Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Each digit from 2 to 9 maps to a small set of letters, just like an old phone keypad. Given a string of digits, the task is to return every possible letter string that could be formed by choosing one mapped letter for each digit.

For example, if the input is "23", the first digit can contribute one of a, b, or c, and the second digit can contribute one of d, e, or f. The answer is every pair that comes from combining those choices.

So this is not really a math problem. It is a systematic combination-building problem.

The key insight

At any position in the digit string, the remaining work always has the same shape:

  • choose one letter for the current digit
  • move to the next digit
  • keep building until one full string is complete

That makes backtracking the most natural solution. A partial string represents one path through the decision tree. Each recursive step adds one character, and when the path length matches the number of digits, one valid answer is finished.

This is also an output-sized problem. If the input has n digits, there can be up to 4^n combinations because some digits map to four letters. No algorithm can avoid spending time proportional to the number of combinations it must return.

How to derive the optimal solution

The brute-force instinct is often vague: “try all possibilities.” The useful refinement is to ask what one choice looks like.

For this problem, one choice means:

  1. Look at the current digit.
  2. Iterate through its available letters.
  3. Append one letter.
  4. Solve the same problem for the next digit.
  5. Remove the letter and try the next option.

That is exactly the backtracking pattern.

The reason it is optimal here is that the output itself is exponential. The solution only does the necessary work to generate each valid string once.

  • Time: O(n * 4^n) in the worst case, because there are up to 4^n results and each finished result has length n
  • Extra space: O(n) for the recursion stack and current path, not counting the returned output

Best way to think about it

Do not think of the problem as “convert digits to letters.”

Think of it as:

  • one digit = one layer in a decision tree
  • one letter choice = one branch
  • one root-to-leaf path = one completed answer

Once that picture is clear, the code becomes a direct translation of the tree traversal.

Python solution

from typing import Dict, List


class PhoneLetterCombinator:
    """Generate all keypad letter combinations for a digit string."""

    DIGIT_TO_LETTERS: Dict[str, str] = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

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

        combinations: List[str] = []
        current_path: List[str] = []
        self._build_combinations(
            digits=digits,
            digit_index=0,
            current_path=current_path,
            combinations=combinations,
        )
        return combinations

    def _build_combinations(
        self,
        digits: str,
        digit_index: int,
        current_path: List[str],
        combinations: List[str],
    ) -> None:
        # A full path means one complete letter combination is ready.
        if digit_index == len(digits):
            combinations.append("".join(current_path))
            return

        current_digit = digits[digit_index]
        candidate_letters = self.DIGIT_TO_LETTERS[current_digit]

        for letter in candidate_letters:
            current_path.append(letter)
            self._build_combinations(
                digits=digits,
                digit_index=digit_index + 1,
                current_path=current_path,
                combinations=combinations,
            )
            current_path.pop()


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        combinator = PhoneLetterCombinator()
        return combinator.generate_combinations(digits)

Interview follow-ups

How would you solve it iteratively instead of with recursion?

An iterative solution builds the answer list layer by layer. Start with [""]. For each digit, replace the current list with every existing prefix extended by each letter for that digit. If the current list is ["a", "b", "c"] and the next digit maps to def, the next list becomes ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

This works because each pass locks in one more position of every combination. It is effectively the same decision tree as backtracking, just processed breadth-first instead of depth-first. The asymptotic cost is the same: the algorithm still has to materialize every answer. The iterative version avoids recursion depth concerns, but it usually allocates larger intermediate lists at each layer.

What if the interviewer asks for the number of combinations, not the combinations themselves?

Then the problem becomes much simpler. There is no need to generate strings. The answer is just the product of the number of choices for each digit. For example, "23" has 3 * 3 = 9 combinations, and "79" has 4 * 4 = 16.

That works because the choices at each digit are independent. Each letter for one digit can pair with every valid letter from the other digits, so the multiplication principle applies directly. The time drops to O(n) and the extra space can be O(1), which is much better than generating the full output when only the count is needed.

How would you handle digits like 0 and 1, or a custom keypad mapping?

The clean design is to avoid hard-coding assumptions into the recursion itself. Keep the recursion generic and inject the digit-to-letters mapping as data. Then the implementation can either reject digits with no mapping, skip them by policy, or support a different keypad entirely.

This works because the search logic only needs one primitive operation: “given the current symbol, what are the valid next characters?” Once that lookup is abstracted, the rest of the algorithm is unchanged. The tradeoff is that input validation becomes a product decision rather than a coding detail, so it is worth stating the chosen behavior explicitly in an interview.

How would you stream results instead of storing them all in memory?

The backtracking structure already visits combinations one at a time, so it can be turned into a generator that yields each finished string instead of appending to a list. That is useful when the caller wants to process combinations incrementally, write them to a file, or stop early after finding enough matches.

This works because only the current path must stay in memory during the depth-first traversal. The extra working space remains O(n) instead of growing with the full output size. The tradeoff is that a streaming interface is less convenient when the caller needs random access or the full list immediately, which is why LeetCode still expects a collected list at the end.

Practical takeaway

This problem is a good example of when exponential time is not a sign of a bad solution. The answer set itself is exponential, so the real goal is to generate each valid combination once with minimal overhead.

Backtracking is the cleanest fit because the recursive state matches the problem statement exactly: one digit position, one partial string, and one finished answer whenever the path reaches the end.