Course4all
Join us on telegram
Home/dsa/Backtracking/Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

Master this topic with zero to advance depth.

Letter Combinations of a Phone Number

Cartesion Product on Strings

This problem asks for the Cartesian product of several sets of characters. Each digit from 2-9 maps to a set of letters (like a telephone keypad).

Key Backtracking Logic

We iterate through the input digits. For the current digit, we try all mapped letters, appending them to our current path, and moving to the next digit.

Decision Tree Width

The width of the tree varies: 3 for most digits (2, 3, 4, 5, 6, 8), and 4 for digits '7' (pqrs) and '9' (wxyz).

Find all letter combinations for a phone number. Includes visual Cartesian product tree.

Medium

Examples

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Approach 1

Level I: Recursive Backtracking

Intuition

Treat the problem as a tree traversal where each digit is a level and each letter is a branch.

Maintain a mapping of digits to letters. At each call backtrack(idx, path), if idx == digits.length, add path to results. Otherwise, iterate through letters of digits[idx] and recurse.

⏱ O(4^N * N) where N is the length of digits.💾 O(N) for recursion stack.

Detailed Dry Run

Dry Run: digits="2" | idx | Digit | Letter | Path | Action | | :-- | :---- | :----- | :--- | :----------------- | | 0 | '2' | 'a' | "a" | Choose 'a', DFS(1) | | 1 | - | - | "a" | Result! (Backtrack)| | 0 | '2' | 'b' | "b" | Choose 'b', DFS(1) | | 1 | - | - | "b" | Result! (Backtrack)| | 0 | '2' | 'c' | "c" | Choose 'c', DFS(1) |
java
class Solution {
    private final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.isEmpty()) return res;
        backtrack(0, new StringBuilder(), digits, res);
        return res;
    }
    private void backtrack(int idx, StringBuilder path, String digits, List<String> res) {
        if (idx == digits.length()) {
            res.add(path.toString());
            return;
        }
        String letters = MAP[digits.charAt(idx) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(idx + 1, path, digits, res);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
Approach 2

Level II: Iterative BFS (Queue-based)

Intuition

Instead of recursion, use a queue to store intermediate combinations.

Initialize queue with an empty string. For each digit, dequeue all strings, append each possible letter for that digit, and enqueue the new strings.

⏱ O(4^N * N)💾 O(4^N)

Detailed Dry Run

digits="23"

  1. Queue: [""]
  2. Digit '2': Dequeue "", Enqueue "a", "b", "c". Queue: ["a", "b", "c"]
  3. Digit '3': Dequeue "a", Enqueue "ad", "ae", "af". Queue: ["b", "c", "ad", "ae", "af"]...
java
class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> queue = new LinkedList<>();
        if (digits.isEmpty()) return queue;
        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            int d = digits.charAt(i) - '0';
            while (queue.peek().length() == i) {
                String s = queue.remove();
                for (char c : map[d].toCharArray()) queue.add(s + c);
            }
        }
        return queue;
    }
}
Approach 3

Level III: Optimized Backtracking (String Sharing / Buffer)

Intuition

In some languages, creating many small strings is expensive. Using a shared buffer can improve performance.

Use a StringBuilder (Java) or a fixed-size array and only convert to result strings at the leaves of the tree.

⏱ O(4^N * N)💾 O(N)

Detailed Dry Run

Same as Level I, but focusing on memory alloc efficiency.

java
// Same as Level I Java code, which already uses StringBuilder for efficiency.
← Previous QuestionSubsets II
Next Question →Word Search