Letter Combinations of a Phone Number

17.Letter Combinations of a Phone Number

Backtracking

String

Recursion

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. Like old phone keypads, each digit maps to a set of letters.

Example:

Input:

digits = "23"

→

Output:

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

Algorithm:

1. Map each digit to its letters
2. Use backtracking to try all combinations
3. Build combinations one character at a time
4. Remove character when backtracking

Complexity:

Time: O(4^N) | Space: O(N) where N is length of digits

Java Solution:

public List letterCombinations(String digits) {
    List res = new ArrayList<>();
    if (digits.length() == 0) return res;
    
    // Map digits to letters
    String[] letters = new String[] {
        "0", "1", "abc", "def", "ghi", "jkl", 
        "mno", "pqrs", "tuv", "wxyz"
    };
    
    backtrack(digits, res, letters, 0, new StringBuilder());
    return res;
}

private void backtrack(String digits, List res, 
        String[] letters, int index, StringBuilder sb) {
    
    // Base case: found a combination
    if (index == digits.length()) {
        res.add(sb.toString());
        return;
    }
    
    // Get letters for current digit
    String curr = letters[digits.charAt(index) - '0'];
    
    // Try each letter
    for (char c : curr.toCharArray()) {
        sb.append(c);  // Choose
        backtrack(digits, res, letters, index + 1, sb);  // Explore
        sb.deleteCharAt(sb.length() - 1);  // Unchoose
    }
}

Python Solution:

def letterCombinations(self, digits: str) -> List[str]:
    if not digits: return []
    
    # Map digits to letters
    letters = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    result = []
    
    def backtrack(index: int, curr: str):
        # Base case: found a combination
        if index == len(digits):
            result.append(curr)
            return
            
        # Try each letter for current digit
        for letter in letters[digits[index]]:
            backtrack(index + 1, curr + letter)
            
    backtrack(0, "")
    return result

C++ Solution:

class Solution {
private:
    void backtrack(string& digits, vector& res,
            vector& letters, int index, string& curr) {
        if (index == digits.length()) {
            res.push_back(curr);
            return;
        }
        
        for (char c : letters[digits[index] - '0']) {
            curr.push_back(c);
            backtrack(digits, res, letters, index + 1, curr);
            curr.pop_back();
        }
    }
    
public:
    vector letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector letters = {
            "0", "1", "abc", "def", "ghi", "jkl", 
            "mno", "pqrs", "tuv", "wxyz"
        };
        
        vector res;
        string curr;
        backtrack(digits, res, letters, 0, curr);
        return res;
    }
};