17. Letter Combinations of a Phone Number

Intuition

Each digit from 2 to 9 maps to a set of letters on a traditional phone keypad. To find all combinations of letters the input digits could represent, we treat this like a combinatorial traversal problem — specifically, a depth-first search (DFS) where we build each possible combination character-by-character.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(4^N)$

Code

// Mapping of digits to corresponding letters (like a phone keypad)
Map<Character, char[]> digitToLettersMap = new HashMap<>();

// List to store all possible combinations
List<String> allCombinations = new LinkedList<>();

// Recursive backtracking helper function
void generateCombinations(String inputDigits, int currentIndex, StringBuilder currentCombination) {
    // Base case: if we've built a full combination, add it to the result list
    if (currentIndex == inputDigits.length()) {
        allCombinations.add(currentCombination.toString());
        return;
    }

    // Get the letters corresponding to the current digit
    char currentDigit = inputDigits.charAt(currentIndex);
    for (char letter : digitToLettersMap.get(currentDigit)) {
        // Choose
        currentCombination.append(letter);

        // Explore
        generateCombinations(inputDigits, currentIndex + 1, currentCombination);

        // Un-choose (backtrack)
        currentCombination.deleteCharAt(currentCombination.length() - 1);
    }
}

public List<String> letterCombinations(String digits) {
    // Edge case: no input
    if (digits.isEmpty()) return Collections.emptyList();

    // Initialize the digit-to-letter mapping
    digitToLettersMap.put('2', new char[]{'a', 'b', 'c'});
    digitToLettersMap.put('3', new char[]{'d', 'e', 'f'});
    digitToLettersMap.put('4', new char[]{'g', 'h', 'i'});
    digitToLettersMap.put('5', new char[]{'j', 'k', 'l'});
    digitToLettersMap.put('6', new char[]{'m', 'n', 'o'});
    digitToLettersMap.put('7', new char[]{'p', 'q', 'r', 's'});
    digitToLettersMap.put('8', new char[]{'t', 'u', 'v'});
    digitToLettersMap.put('9', new char[]{'w', 'x', 'y', 'z'});

    // Begin backtracking from index 0 with an empty combination
    generateCombinations(digits, 0, new StringBuilder());

    return allCombinations;
}