LeetCode 17 - Letter Combinations of a Phone Number

LeetCode Problem 17

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking

Solution

Problem Understanding

The problem gives a string of digits where each digit is between 2 and 9. Each digit corresponds to a set of letters on a traditional phone keypad:

• 2 -> "abc"
• 3 -> "def"
• 4 -> "ghi"
• 5 -> "jkl"
• 6 -> "mno"
• 7 -> "pqrs"
• 8 -> "tuv"
• 9 -> "wxyz"

We must generate every possible letter combination that can be formed by choosing one letter for each digit in the input string.

For example, if the input is "23", then:

• 2 can produce a, b, or c
• 3 can produce d, e, or f

We combine every option from the first digit with every option from the second digit:

• ad, ae, af
• bd, be, bf
• cd, ce, cf

The output can be returned in any order.

The constraints are small:

• 1 <= digits.length <= 4
• Each character is between '2' and '9'

Since the maximum length is only 4, the total number of combinations is manageable. The largest branching factor occurs for digits 7 and 9, which each map to 4 letters. In the worst case, we generate 4^4 = 256 combinations.

One important edge case is an empty input string. Even though the official constraints say the length is at least 1, many implementations still handle the empty string defensively because LeetCode sometimes tests it internally. The correct output for an empty input is an empty list.

Another important detail is that digits 0 and 1 never appear. That means every digit always has a valid letter mapping.

Approaches

Brute Force Approach

A brute force solution would manually generate all possible combinations by nesting loops for every digit position.

For example:

• One loop for the first digit
• Another loop for the second digit
• Another loop for the third digit
• Another loop for the fourth digit

This works because the input length is at most 4. However, this approach is not scalable or maintainable. The number of loops depends on the input length, so the code becomes awkward and repetitive.

It also does not generalize naturally if the problem constraints change.

Key Insight

This problem is fundamentally about generating all possible paths through a decision tree.

At each digit:

• We choose one possible letter
• Then recursively process the next digit

This is exactly what backtracking is designed for.

Backtracking works well because:

• We build combinations incrementally
• At every step we know the current partial combination
• Once a combination reaches the same length as the input digits, it is complete
• The recursion naturally explores every valid possibility

Instead of hardcoding nested loops, we use recursion to dynamically handle any input length.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(4^n)	Requires manually nested loops, not scalable
Optimal	O(4^n)	O(4^n)	Uses backtracking to systematically generate combinations

Here, n is the number of digits.

Algorithm Walkthrough

1. Create a mapping from digits to letters.

We store the phone keypad relationships in a hash map. This allows constant-time lookup for the letters corresponding to each digit. 2. Handle the empty input case.

If the input string is empty, return an empty list immediately. There are no digits to process, so there are no combinations. 3. Initialize a result list.

This list will store every completed combination. 4. Define a recursive backtracking function.

The function keeps track of:

• The current index in the digit string
• The current partial combination being built

5. Check whether a combination is complete.

If the current combination length equals the number of digits, then we have selected one letter for every digit.

At this point:

• Add the completed string to the result list
• Return to explore other possibilities

6. Look up the current digit's letters.

Using the current digit index, retrieve all possible letters from the keypad mapping. 7. Try every possible letter.

For each letter:

• Add it to the current combination
• Recursively process the next digit
• Remove the letter afterward so other choices can be explored

This "choose, explore, unchoose" structure is the core of backtracking. 8. Continue until all paths are explored.

The recursion explores every valid combination exactly once.

Why it works

The algorithm maintains the invariant that the current partial string always represents a valid prefix of some final answer.

At every recursive step, we append one valid letter corresponding to the current digit. Since we explore all letters for every digit position, every possible combination is generated.

The recursion stops only when the combination length matches the digit string length, guaranteeing that every returned string is complete and valid.

Python Solution

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        digit_to_letters = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []

        def backtrack(index: int, current_combination: str) -> None:
            if index == len(digits):
                result.append(current_combination)
                return

            current_digit = digits[index]
            possible_letters = digit_to_letters[current_digit]

            for letter in possible_letters:
                backtrack(index + 1, current_combination + letter)

        backtrack(0, "")

        return result

The implementation starts by handling the empty input case. Returning immediately avoids unnecessary recursion and matches the expected behavior.

The digit_to_letters dictionary stores the phone keypad mapping. A dictionary is the ideal choice because it provides direct lookup from a digit to its associated letters.

The result list collects all completed combinations.

The recursive backtrack function takes two parameters:

• index, the current digit position being processed
• current_combination, the string built so far

When index reaches len(digits), the combination is complete. The function appends it to the result list and stops exploring deeper.

Otherwise, the function retrieves all possible letters for the current digit. It iterates through those letters and recursively builds longer combinations.

The recursive call advances to the next digit while extending the current combination with the chosen letter.

Finally, the algorithm begins recursion with:

backtrack(0, "")

This means:

• Start at digit index 0
• Start with an empty combination

Go Solution

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}

	digitToLetters := map[byte]string{
		'2': "abc",
		'3': "def",
		'4': "ghi",
		'5': "jkl",
		'6': "mno",
		'7': "pqrs",
		'8': "tuv",
		'9': "wxyz",
	}

	result := []string{}

	var backtrack func(index int, currentCombination string)

	backtrack = func(index int, currentCombination string) {
		if index == len(digits) {
			result = append(result, currentCombination)
			return
		}

		currentDigit := digits[index]
		possibleLetters := digitToLetters[currentDigit]

		for _, letter := range possibleLetters {
			backtrack(index+1, currentCombination+string(letter))
		}
	}

	backtrack(0, "")

	return result
}

The Go implementation follows the same recursive structure as the Python version.

One difference is that Go strings are immutable byte sequences, so digits are accessed using digits[index], which returns a byte.

The keypad mapping therefore uses map[byte]string instead of a map with string keys.

Another difference is that Go requires explicit function variable declaration before assigning a recursive anonymous function:

var backtrack func(index int, currentCombination string)

The result slice is initialized as an empty slice rather than nil, ensuring a consistent return value.

Worked Examples

Example 1

Input:

digits = "23"

Digit mappings:

• 2 -> "abc"
• 3 -> "def"

Initial state:

Variable	Value
result	[]
currentCombination	""
index	0

Step-by-step recursion:

Step	Index	Current Combination	Action
1	0	""	Process digit 2
2	1	"a"	Process digit 3
3	2	"ad"	Complete combination
4	2	"ae"	Complete combination
5	2	"af"	Complete combination
6	1	"b"	Process digit 3
7	2	"bd"	Complete combination
8	2	"be"	Complete combination
9	2	"bf"	Complete combination
10	1	"c"	Process digit 3
11	2	"cd"	Complete combination
12	2	"ce"	Complete combination
13	2	"cf"	Complete combination

Final result:

["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input:

digits = "2"

Digit mapping:

• 2 -> "abc"

Execution:

Step	Index	Current Combination	Action
1	0	""	Process digit 2
2	1	"a"	Complete combination
3	1	"b"	Complete combination
4	1	"c"	Complete combination

Final result:

["a", "b", "c"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(4^n)	Each digit can contribute up to 4 choices
Space	O(4^n)	Output storage dominates space usage

The recursion tree branches up to 4 times at each level because digits 7 and 9 each map to 4 letters.

If the input length is n, the total number of generated combinations is at most 4^n.

Each valid combination must be constructed and stored, so both time and output space complexity are proportional to the number of generated combinations.

The recursion stack itself only uses O(n) space, but the output list dominates overall memory usage.

Test Cases

solution = Solution()

# Basic two-digit example
assert sorted(solution.letterCombinations("23")) == sorted([
    "ad", "ae", "af",
    "bd", "be", "bf",
    "cd", "ce", "cf"
])

# Single digit input
assert sorted(solution.letterCombinations("2")) == sorted([
    "a", "b", "c"
])

# Digit with four letters
assert sorted(solution.letterCombinations("7")) == sorted([
    "p", "q", "r", "s"
])

# Two digits with four-letter mappings
assert len(solution.letterCombinations("79")) == 16

# Empty input edge case
assert solution.letterCombinations("") == []

# Maximum length input
assert len(solution.letterCombinations("9999")) == 256

# Mixed digits
assert len(solution.letterCombinations("234")) == 27

# Verify actual values for small input
assert sorted(solution.letterCombinations("22")) == sorted([
    "aa", "ab", "ac",
    "ba", "bb", "bc",
    "ca", "cb", "cc"
])

Test	Why
"23"	Standard multi-digit example
"2"	Smallest non-empty valid input
"7"	Tests digit with 4 letters
"79"	Tests maximum branching behavior
""	Defensive empty input handling
"9999"	Maximum constraint size
"234"	Multiple recursive levels
"22"	Verifies Cartesian product generation

Edge Cases

Empty Input String

An empty string is a common edge case that can easily produce incorrect output if not handled carefully. A naive recursive implementation might return [""] instead of [].

The implementation explicitly checks:

if not digits:
    return []

This guarantees the correct behavior.

Digits With Four Letters

Digits 7 and 9 map to four letters instead of three:

• 7 -> "pqrs"
• 9 -> "wxyz"

An incorrect implementation might assume every digit has exactly three letters, causing missing combinations.

The solution avoids this issue by dynamically iterating over the mapped string for each digit rather than assuming a fixed size.

Maximum Input Length

The longest valid input has length 4. Although this is small, it still generates many combinations:

4^4 = 256

A poorly implemented solution might repeatedly copy large intermediate structures or use inefficient string operations.

The recursive backtracking approach efficiently builds combinations one step at a time and only stores completed results.