Letter Combinations of Phone Number

Problem Statement

Given a string of digits (2-9), return all possible letter combinations that the number could represent, based on a phone keypad mapping (e.g., 2 = "abc", 3 = "def"). This medium-level problem uses recursion and backtracking to combine characters from each digit’s options—imagine texting every possible word from a numeric code!

Example

Input: digits = "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] (all combos of 2="abc", 3="def")

Input: digits = "2"

Output: ["a", "b", "c"] (just 2’s letters)

Code

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

def letter_combinations(digits):
    if not digits:
        return []
    
    keypad = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    
    def backtrack(index, current):
        if index == len(digits):
            result.append(current)
            return
        for char in keypad[digits[index]]:
            backtrack(index + 1, current + char)
    
    result = []
    backtrack(0, "")
    return result

# Example usage
print(letter_combinations("23"))  # ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
print(letter_combinations("2"))   # ["a", "b", "c"]
            

function letterCombinations(digits) {
    if (!digits) return [];
    
    const keypad = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    };
    
    function backtrack(index, current) {
        if (index === digits.length) {
            result.push(current);
            return;
        }
        for (let char of keypad[digits[index]]) {
            backtrack(index + 1, current + char);
        }
    }
    
    let result = [];
    backtrack(0, "");
    return result;
}

// Example usage
console.log(letterCombinations("23")); // ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
console.log(letterCombinations("2"));  // ["a", "b", "c"]
            

Explanation

• Base Case: When index equals digits length, add the current combination.
• Recursive Step: For each letter mapped to the current digit, append it and recurse.
• Backtracking: Build strings by exploring all possibilities, no need to undo as we pass new strings.
• Flow Example (digits="23"): "" → "a" → "ad", "ae", "af"; "b" → "bd", "be", "bf"; etc.
• Mapping: Uses a predefined keypad dictionary/array for digit-to-letter conversion.

Note