Letter Combinations of a Phone Number

How it works

Instead of using recursion, we build combinations level by level.

Start with an empty string. For each digit:

• Take all combinations built so far
• Append every possible character mapped to the current digit
• This creates a new list of combinations

This is similar to BFS / level-wise expansion:

• Each digit adds a new "layer" of characters
• Combinations grow step by step until all digits are processed

Steps

1. If the input string is empty, return an empty list.
2. Initialize the result list with one empty string: [""].
3. Create a digit-to-characters mapping (phone keypad).
4. For each digit in the input:
   • Create a temporary list.
   • For every existing string in the result:
     • Append each possible character of the current digit.
     • Store the new strings in the temporary list.
   • Replace the result list with the temporary list.
5. After processing all digits, return the result list.

Complexity

• Time complexity: O(n * 4 ^ n)
• Space complexity:
  • O(n) extra space.
  • O(n * 4 ^ n) space for the output list.

Things to watch for

Not Handling Empty Input

When digits is empty, returning [""] (list with empty string) is wrong. The correct answer is [] (empty list) since there are no combinations to form.

Incorrect Digit-to-Letter Mapping

Digit 7 maps to "pqrs" (4 letters) and digit 9 maps to "wxyz" (4 letters), not 3 letters each. Using "qprs" instead of "pqrs" for digit 7 produces wrong orderings.

Off-by-One in Digit Indexing

When using an array for digit mapping, digits 0 and 1 have no letters. Forgetting this offset or incorrectly computing digit - '0' leads to index errors or wrong character mappings.

from typing import List

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

        res = [""]
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }

        for digit in digits:
            tmp = []
            for curStr in res:
                for c in digitToChar[digit]:
                    tmp.append(curStr + c)
            res = tmp
        return res

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

        vector<string> res = {""};
        vector<string> digitToChar = {
            "", "", "abc", "def", "ghi", "jkl",
            "mno", "qprs", "tuv", "wxyz"
        };

        for (char digit : digits) {
            vector<string> tmp;
            for (string &curStr : res) {
                for (char c : digitToChar[digit - '0']) {
                    tmp.push_back(curStr + c);
                }
            }
            res = tmp;
        }
        return res;
    }
};