Problem #17: Letter Combinations of a Phone Number

Intuition & Strategy Breakdown

Use recursive backtracking. Map each digit to its corresponding phone characters and build combinations level by level, adding a completed string when the target length is reached.

Python Solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        phone = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }
        
        res = []
        
        def backtrack(index, path):
            if len(path) == len(digits):
                res.append("".join(path))
                return
            
            letters = phone[digits[index]]
            for letter in letters:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()
        
        backtrack(0, [])
        return res

Java Solution

class Solution {
    public List letterCombinations(String digits) {
        List res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
        
        String[] mapping = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        
        backtrack(res, digits, "", 0, mapping);
        return res;
    }
    
    private void backtrack(List res, String digits, String current, int index, String[] mapping) {
        if (index == digits.length()) {
            res.add(current);
            return;
        }
        
        String letters = mapping[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            backtrack(res, digits, current + c, index + 1, mapping);
        }
    }
}