Letter Combinations of a Phone Number

LeetCode 17: Letter Combinations of a Phone Number Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses backtracking to simulate a dynamic number of nested loops, exploring every possible letter combination for the given sequence of digits.

The "Letter Combinations of a Phone Number" problem asks us to transform a string of digits (from 2 to 9) into a list of all possible letter strings that the number could represent, based on the standard telephone keypad mapping. For example, the digit '2' maps to "abc" and '3' maps to "def". If the input is "23", we must produce combinations like "ad", "ae", "af", "bd", and so on.

This is a classic combinatorial problem often found in technical interviews. The LeetCode 17 solution requires generating all permutations where exactly one letter is chosen for each digit position.

Brute Force Approach for Letter Combinations of a Phone Number

A naive attempt to solve this problem usually involves iterative loops. If we know the input has exactly two digits (e.g., "23"), we can write two nested for loops: one iterating through the letters of '2' and the inner one iterating through the letters of '3'.

Pseudo-code for Fixed Length

// Works ONLY if input length is exactly 2
result = []
letters1 = map[digits[0]]
letters2 = map[digits[1]]

for char1 in letters1:
    for char2 in letters2:
        result.add(char1 + char2)

Analysis and Failure

While this approach works for a fixed input length, it fails fundamentally when the input length is variable. The constraint 0 <= digits.length <= 4 implies the length changes at runtime.

To handle an input of length $N$ using an iterative brute force approach, we would need $N$ nested loops. Since we cannot write code with a dynamic number of nested loops, the standard iterative brute force approach is implementationally infeasible. This limitation forces us to use recursion (or an explicit stack) to simulate dynamic nesting.

Algorithm Strategy: Backtracking Patterns

To implement the solution using the Backtracking pattern, we maintain the following state:

1. Mapping: A constant lookup table (hash map or array) linking digits '2'-'9' to their respective characters.
2. Current Path: A mutable string or buffer that holds the combination being built.
3. Index Pointer: An integer tracking which digit in the input string we are currently processing.

The Recursive Function: The function backtrack(index, current_path) performs these logic steps:

1. Base Case: If index equals the length of the input digits, current_path is complete. Add it to the results list and return.
2. Recursive Step:
   • Retrieve the digit at digits[index].
   • Look up the corresponding letters (e.g., '2' -> "abc").
   • Iterate through each letter:
     • Include: Append the letter to current_path.
     • Explore: Call backtrack(index + 1, current_path).
     • Backtrack: Remove the letter from current_path to restore the state for the next iteration.

Execution Flow

Let's trace the execution for digits = "23".

1. Initialize: Map = {2: "abc", 3: "def"...}, Result = [], Path = "". Call backtrack(0).
2. Depth 0 (Digit '2'):
   • Loop selects 'a'. Path becomes "a".
   • Recurse to backtrack(1).
3. Depth 1 (Digit '3'):
   • Loop selects 'd'. Path becomes "ad".
   • Recurse to backtrack(2).
4. Depth 2 (Base Case):
   • Index 2 == Length 2. Add "ad" to Result. Return.
5. Backtrack to Depth 1:
   • Remove 'd'. Path is "a".
   • Loop selects 'e'. Path becomes "ae".
   • Recurse to backtrack(2).
   • Add "ae" to Result. Return.
6. Backtrack to Depth 1:
   • Remove 'e'. Path is "a".
   • Loop selects 'f'. Path becomes "af".
   • Recurse to backtrack(2).
   • Add "af" to Result. Return.
7. Backtrack to Depth 0:
   • Remove 'f', then remove 'a'. Path is "".
   • Loop selects 'b'. Path becomes "b".
   • Repeat process for the 'b' branch.

Proof of Correctness

The correctness of this algorithm relies on the exhaustiveness of the Depth-First Search strategy.

1. Coverage: The algorithm iterates through every possible character mapping for digits[i] before moving to digits[i+1]. This guarantees that if a combination exists, the recursion will traverse the path to generate it.
2. Constraint Satisfaction: The base case triggers only when the path length equals the input length, ensuring all generated strings are of the correct size.
3. Invariant: At any recursive step i, the prefix of the combination 0 to i-1 remains constant while we explore all variations for position i and beyond.

Pattern Reuse Notes

The Backtracking pattern used here is fundamental for combinatorial problems.

• LeetCode 77: Combinations - Uses the same include/exclude logic to select $k$ numbers from $n$.
• LeetCode 78: Subsets - Explores the power set, deciding at each step whether to include an element or not.
• LeetCode 90: Subsets II - Same as Subsets, but requires handling duplicates by sorting and skipping identical elements during the backtracking phase.

In all these cases, the backtrack(index, current_path) structure remains the primary driver of the solution.

Reference Implementation

C++ Solution for LeetCode 17

1class Solution {
2public:
3    // Mapping from digit to corresponding letters
4    const vector<string> KEYPAD = {
5        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
6    };
7
8    vector<string> letterCombinations(string digits) {
9        if (digits.empty()) {
10            return {};
11        }
12
13        vector<string> result;
14        string currentPath;
15        backtrack(digits, 0, currentPath, result);
16        return result;
17    }
18
19private:
20    void backtrack(const string& digits, int index, string& currentPath, vector<string>& result) {
21        // Base Case: If the path is the same length as digits, we have a complete combination
22        if (index == digits.length()) {
23            result.push_back(currentPath);
24            return;
25        }
26
27        // Get the letters corresponding to the current digit
28        int digit = digits[index] - '0';
29        const string& letters = KEYPAD[digit];
30
31        // Iterate through each letter and recurse
32        for (char letter : letters) {
33            currentPath.push_back(letter);       // Include
34            backtrack(digits, index + 1, currentPath, result); // Explore
35            currentPath.pop_back();              // Backtrack
36        }
37    }
38};

Java Solution for LeetCode 17

1import java.util.ArrayList;
2import java.util.List;
3import java.util.Map;
4
5class Solution {
6    // Static mapping for the keypad
7    private static final String[] KEYPAD = {
8        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
9    };
10
11    public List<String> letterCombinations(String digits) {
12        List<String> result = new ArrayList<>();
13        
14        // Edge case: empty input
15        if (digits == null || digits.length() == 0) {
16            return result;
17        }
18
19        // Use StringBuilder for efficient mutable string manipulation
20        backtrack(result, digits, new StringBuilder(), 0);
21        return result;
22    }
23
24    private void backtrack(List<String> result, String digits, StringBuilder currentPath, int index) {
25        // Base Case: Path length matches digits length
26        if (index == digits.length()) {
27            result.add(currentPath.toString());
28            return;
29        }
30
31        // Identify current digit and its letters
32        int digit = digits.charAt(index) - '0';
33        String letters = KEYPAD[digit];
34
35        // Loop through letters
36        for (char letter : letters.toCharArray()) {
37            currentPath.append(letter);          // Include
38            backtrack(result, digits, currentPath, index + 1); // Explore
39            currentPath.deleteCharAt(currentPath.length() - 1); // Backtrack
40        }
41    }
42}

Python Solution for LeetCode 17

1class Solution:
2    def letterCombinations(self, digits: str) -> List[str]:
3        if not digits:
4            return []
5        
6        # Mapping for the keypad
7        keypad = {
8            "2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
9            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
10        }
11        
12        result = []
13        
14        def backtrack(index, current_path):
15            # Base Case: If the path is complete
16            if index == len(digits):
17                result.append("".join(current_path))
18                return
19            
20            # Get letters for the current digit
21            current_digit = digits[index]
22            letters = keypad[current_digit]
23            
24            for letter in letters:
25                current_path.append(letter)      # Include
26                backtrack(index + 1, current_path) # Explore
27                current_path.pop()               # Backtrack
28        
29        # Start recursion with index 0 and empty list for path
30        backtrack(0, [])
31        return result