Letter Combinations of a Phone Number

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

| Digit | Letters |

|-------|---------|

| 2 | abc |

| 3 | def |

| 4 | ghi |

| 5 | jkl |

| 6 | mno |

| 7 | pqrs |

| 8 | tuv |

| 9 | wxyz |

Understanding the Problem

This is a classic Combinatorial Generation problem. We are not looking for a specific combination (like a password), but rather all valid combinations. The input is a sequence of digits, and the output is a sequence of strings.

Key Observations

1. Input Length: The number of digits determines the depth of recursion. If the input has n digits, the recursion depth will be n.
2. Branching Factor: Each digit maps to 3 or 4 letters. This means at each step of the recursion, we have multiple choices (branches).
3. Combination Order: The order of combinations matters in terms of generation (e.g., "ad" comes before "ae"), but the problem allows any order in the final output.

The Backtracking Approach

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Why Backtracking?

We can solve this using simple loops, but Backtracking is the most natural fit because:

1. We are building a string character by character.
2. We need to explore all possible paths (all combinations).
3. Once we reach the end of the digits, we have found a valid combination.

The Algorithm

1. Mapping: Create a dictionary/hash map to store the digit-to-letter mappings.
2. Base Case: If the current index is equal to the length of the input string, we have successfully built a combination. Add it to our result list.
3. Recursive Step: For the current digit, iterate through all its corresponding letters. For each letter, append it to the current combination and recursively call the function for the next index.
4. Backtracking: The recursion automatically handles "backtracking" because when a recursive call returns, the function continues to the next letter in the loop, effectively removing the last added letter and trying a different one.

Step-by-Step Walkthrough (Input: "23")

1. Start: index = 0, current = ""
2. Digit '2' (abc):

• Pick 'a': Recurse with index=1, current="a"
• Pick 'b': Recurse with index=1, current="b"
• Pick 'c': Recurse with index=1, current="c"

1. Digit '3' (def):

• From 'a': Pick 'd' -> "ad", Pick 'e' -> "ae", Pick 'f' -> "af". (Base case reached)
• From 'b': Pick 'd' -> "bd", Pick 'e' -> "be", Pick 'f' -> "bf". (Base case reached)
• From 'c': Pick 'd' -> "cd", Pick 'e' -> "ce", Pick 'f' -> "cf". (Base case reached)

Implementation

TypeScript/JavaScript

function letterCombinations(digits: string): string[] {
  // Edge case: empty input
  if (!digits) return [];

  // Mapping of digits to letters
  const digitMap: { [key: string]: string } = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
  };

  const result: string[] = [];

  // Recursive Backtracking Function
  function backtrack(index: number, currentCombination: string) {
    // Base Case: If we have processed all digits
    if (index === digits.length) {
      result.push(currentCombination);
      return;
    }

    // Get the current digit
    const currentDigit = digits[index];
    // Get the corresponding letters
    const letters = digitMap[currentDigit];

    // Iterate through each letter for the current digit
    for (const letter of letters) {
      // Add letter to current combination
      backtrack(index + 1, currentCombination + letter);
    }
  }

  // Start the recursion
  backtrack(0, "");

  return result;
}

Python

def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []

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

    result = []

    def backtrack(index: int, current: str):
        if index == len(digits):
            result.append(current)
            return

        for letter in digit_map[digits[index]]:
            backtrack(index + 1, current + letter)

    backtrack(0, "")
    return result

Complexity Analysis

Time Complexity: O(3^N * 4^M)

• N: The number of digits in the input string.
• M: The number of digits that map to 4 letters (7 and 9).

For every digit, we have a branching factor. Most digits have 3 letters, but digits 7 and 9 have 4 letters.

• If all digits had 3 letters, the total combinations would be 3^N.
• Since 7 and 9 have 4 letters, we multiply by 4^M.
• Additionally, we spend O(N) time to build the string at each level (concatenation), but this is often dominated by the exponential growth of the combinations.

Space Complexity: O(N)

• Recursion Stack: The maximum depth of the recursion is equal to the number of digits N.
• Output Storage: We store all combinations in the result array. The total number of characters stored is O(3^N 4^M N), but this is the output size, not auxiliary space. The auxiliary space (excluding output) is O(N).

Optimization Tips

1. String Concatenation: In languages like Python or JavaScript, string concatenation inside a loop (current + letter) can be inefficient because strings are immutable. It creates a new string object every time. While acceptable for small inputs, for very large inputs, it is better to use a list/array to build the string and join it at the end.

Optimized Python approach: Use a list path to store characters, append at the end, and pop (backtrack) when returning.

1. Iterative Approach (Queue): You can solve this iteratively using a queue. Start with an empty string. For each digit, take all current strings in the queue, append each letter of the digit to them, and add the new strings back to the queue. This effectively simulates the backtracking tree without the call stack overhead.

Common Mistakes

1. Ignoring the Empty Input: If the input string is empty, the function should return an empty array, not [""] or null.
2. Incorrect Base Case: The base case must be when index equals the length of the digits string, not when the current combination is empty.
3. Modifying the Input Map: Ensure you are not modifying the original mapping dictionary during the recursion.

Real-World Applications

1. T9 Texting: The algorithm is directly used in older mobile phones to predict words based on pressed keys.
2. Dialing Codes: Generating all possible combinations for area codes or extension numbers.
3. Password Generation: Creating all possible variations of a numeric PIN based on a set of rules.

Summary

The "Letter Combinations of a Phone Number" problem is a quintessential example of Backtracking. It teaches us how to systematically explore a state space tree, where each node represents a partial solution. By defining a clear base case (reaching the end of the input) and a recursive step (adding a letter and moving to the next digit), we can efficiently generate all valid combinations.