LeetCode 17: Letter Combinations of a Phone Number

Problem Restatement

We are given a string digits.

Each character is a digit from 2 to 9.

Each digit maps to letters like on a phone keypad:

We need to return all possible letter combinations that the digit string could represent.

The answer may be returned in any order. The statement notes that 1 does not map to any letters. The input digits are from 2 to 9.

Input and Output

Example function shape:

def letterCombinations(digits: str) -> list[str]:
    ...

Examples

Example 1:

digits = "23"

Digit 2 maps to:

a, b, c

Digit 3 maps to:

d, e, f

All combinations are:

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

Output:

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

Example 2:

digits = ""

There are no digits, so there are no combinations.

Output:

[]

Example 3:

digits = "2"

Output:

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

First Thought: Nested Loops

For digits = "23", we can write two loops:

for a in "abc":
    for b in "def":
        result.append(a + b)

This works only when the input has exactly two digits.

If the input has three digits, we need three loops.

If the input has four digits, we need four loops.

The number of loops depends on the input length, so fixed nested loops are not a good general solution.

Key Insight

This is a combination-building problem.

At each digit, choose one letter from that digit’s mapped letters.

For example, with:

digits = "23"

we first choose one of:

a, b, c

Then for each choice, choose one of:

d, e, f

Each path from the first digit to the last digit forms one complete combination.

This is exactly what backtracking does.

Backtracking Tree

For:

digits = "23"

The tree is:

start
  a
    ad
    ae
    af
  b
    bd
    be
    bf
  c
    cd
    ce
    cf

Each level corresponds to one digit.

Each edge chooses one letter.

When the path length equals len(digits), we have one complete combination.

Algorithm

1. If digits is empty, return [].
2. Store the digit-to-letter mapping.
3. Create an empty result list.
4. Define a backtracking function with:
   • index: which digit we are processing
   • path: letters chosen so far
5. If index == len(digits), add path to the result.
6. Otherwise:
   • get the letters for digits[index]
   • try each letter
   • recurse to the next index
7. Return the result list.

Correctness

Each recursive level handles exactly one digit.

For the digit at position index, the algorithm tries every letter mapped from that digit.

So after processing k digits, path contains one valid choice for each of the first k digits.

When index == len(digits), the path contains exactly one letter for every input digit, so it is a valid complete combination.

The algorithm explores every letter choice for every digit, so no valid combination is missed.

It appends a result only when one letter has been chosen per digit, so no invalid partial combination is returned.

Therefore the algorithm returns exactly all possible letter combinations.

Complexity

Here:

n = len(digits)

The recursion stack itself uses O(n) space.

The factor 4 comes from digits 7 and 9, which each map to four letters.

Implementation

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

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

        result = []

        def backtrack(index: int, path: list[str]) -> None:
            if index == len(digits):
                result.append("".join(path))
                return

            digit = digits[index]

            for letter in phone[digit]:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()

        backtrack(0, [])

        return result

Code Explanation

Handle the empty input first:

if not digits:
    return []

The mapping follows the phone keypad:

phone = {
    "2": "abc",
    "3": "def",
    ...
    "9": "wxyz",
}

The result list stores complete combinations:

result = []

The helper function:

backtrack(index, path)

means:

We have already chosen letters for digits before index.
Now choose a letter for digits[index].

When all digits have been processed:

if index == len(digits):
    result.append("".join(path))
    return

Try every possible letter for the current digit:

for letter in phone[digit]:

Choose a letter:

path.append(letter)

Recurse:

backtrack(index + 1, path)

Undo the choice:

path.pop()

This lets the next letter reuse the same path list.

Finally:

return result

Testing

def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(s.letterCombinations("23")) == normalize([
        "ad", "ae", "af",
        "bd", "be", "bf",
        "cd", "ce", "cf",
    ])

    assert s.letterCombinations("") == []
    assert normalize(s.letterCombinations("2")) == ["a", "b", "c"]

    assert normalize(s.letterCombinations("7")) == [
        "p", "q", "r", "s",
    ]

    assert normalize(s.letterCombinations("79")) == normalize([
        "pw", "px", "py", "pz",
        "qw", "qx", "qy", "qz",
        "rw", "rx", "ry", "rz",
        "sw", "sx", "sy", "sz",
    ])

    print("all tests passed")

run_tests()