Letter Combinations of a Phone Number

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.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = “23” Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Example 2:

Input: digits = “2” Output: [“a”,“b”,“c”]

Constraints:

• 1 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Approach: Backtracking (DFS)

Algorithm

1. Build a mapping from each digit to its letters
2. Use a recursive function that builds combinations one letter at a time
3. When the current combination has the same length as digits, add it to the result
4. Otherwise, iterate over the letters of the current digit and recurse
5. Backtrack by removing the last letter before trying the next one

Time & Space Complexity

• Time Complexity: O(4^n) - each digit maps to up to 4 letters
• Space Complexity: O(n) - recursion depth and the current combination

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class LetterCombinationsOfAPhoneNumber {

    private static final String[] KEYPAD = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    /**
     * Return all possible letter combinations for the given digits.
     * @param digits Input string of digits 2-9
     * @return List of letter combinations
     */
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.isEmpty()) {
            return result;
        }

        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private static void backtrack(String digits, int index,
                                  StringBuilder current, List<String> result) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        String letters = KEYPAD[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            current.append(letters.charAt(i));
            backtrack(digits, index + 1, current, result);
            current.deleteCharAt(current.length() - 1);
        }
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: digits = \"23\"");
        System.out.println("Output: " + letterCombinations("23"));
        // Expected: [ad, ae, af, bd, be, bf, cd, ce, cf]

        System.out.println("Input: digits = \"2\"");
        System.out.println("Output: " + letterCombinations("2"));
        // Expected: [a, b, c]
    }
}

Example Walkthrough

For digits = "23":

1. ‘2’ -> letters “abc”
2. ‘3’ -> letters “def”
3. Combining gives: ad, ae, af, bd, be, bf, cd, ce, cf

Key Points

1. Tree of Choices: Each digit branches into its mapped letters
2. Backtracking Pattern: Append -> recurse -> remove
3. Small Input: digits.length <= 4, so the output is at most 4^4 = 256 combinations
4. Empty Input: Return an empty list for empty digits
5. Mapping: Digits 7 and 9 have four letters each; 0 and 1 map to nothing