# 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:

| Digit | Letters |
|---|---|
| `2` | `abc` |
| `3` | `def` |
| `4` | `ghi` |
| `5` | `jkl` |
| `6` | `mno` |
| `7` | `pqrs` |
| `8` | `tuv` |
| `9` | `wxyz` |

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

| Item | Meaning |
|---|---|
| Input | A string `digits` |
| Output | All possible letter combinations |
| Digit range | Each digit is from `2` to `9` |
| Empty input | Return `[]` |
| Order | Any order is accepted |

Example function shape:

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

## Examples

Example 1:

```text
digits = "23"
```

Digit `2` maps to:

```text
a, b, c
```

Digit `3` maps to:

```text
d, e, f
```

All combinations are:

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

Output:

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

Example 2:

```text
digits = ""
```

There are no digits, so there are no combinations.

Output:

```text
[]
```

Example 3:

```text
digits = "2"
```

Output:

```text
["a","b","c"]
```

## First Thought: Nested Loops

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

```python
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:

```text
digits = "23"
```

we first choose one of:

```text
a, b, c
```

Then for each choice, choose one of:

```text
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:

```text
digits = "23"
```

The tree is:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(4^n * n)` | There are at most `4^n` combinations, and each output string has length `n` |
| Space | `O(4^n * n)` | The result list stores all combinations |

Here:

```text
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

```python
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:

```python
if not digits:
    return []
```

The mapping follows the phone keypad:

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

The result list stores complete combinations:

```python
result = []
```

The helper function:

```python
backtrack(index, path)
```

means:

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

When all digits have been processed:

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

Try every possible letter for the current digit:

```python
for letter in phone[digit]:
```

Choose a letter:

```python
path.append(letter)
```

Recurse:

```python
backtrack(index + 1, path)
```

Undo the choice:

```python
path.pop()
```

This lets the next letter reuse the same path list.

Finally:

```python
return result
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `"23"` | Standard two-digit example |
| `""` | Empty input returns no combinations |
| `"2"` | Single digit with three letters |
| `"7"` | Single digit with four letters |
| `"79"` | Both digits have four letters |