78.Letter Combinations of a Phone Number

MediumBacktracking · 8/9

Problem

Given a string digits containing digits 2–9, return all letter combinations the number could represent on a classic phone keypad. The answer may be in any order.

The mapping is: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz. If digits is empty, return an empty list.

Examples

Input:  digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 3 letters for '2' times 3 letters for '3' = 9 strings.

Input:  digits = ""
Output: []

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

Constraints

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

💡 Key Insight

This is a Cartesian product: position i of the answer is any letter of digits[i]'s group. Build strings one digit at a time — either breadth-first (extend every partial string with every letter of the next digit) or depth-first with a single StringBuilder that you append to and then trim back. There are up to 4^n results of length n, so O(n · 4^n) is unavoidable.

Iterative Queue (BFS)

TimeO(n · 4^n)SpaceO(n · 4^n)

Intuition

Start with one empty prefix. For each digit, replace every prefix with all of its one-letter extensions. After processing all digits, the prefixes are exactly the answers.

Algorithm

If digits is empty, return [].
result = [""].
For each digit d:
- next = []; for each prefix in result and each letter of map[d], add prefix + letter to next.
- result = next.
Return result.

Visualization

digits = "23"

start        : [""]
digit '2'    : ["a", "b", "c"]
digit '3'    : ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Code

java

import java.util.*;

class Solution {
    private static final String[] KEYS = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        result.add("");
        for (char d : digits.toCharArray()) {
            List<String> next = new ArrayList<>();
            for (String prefix : result) {
                for (char letter : KEYS[d - '0'].toCharArray()) {
                    next.add(prefix + letter); // extend each prefix by one letter
                }
            }
            result = next;
        }
        return result;
    }
}

Complexity

Time: O(n · 4^n) — up to 4^n strings, each built by copying a prefix of length up to n.
Space: O(n · 4^n) — the previous round's list is held while the next is built.

Backtracking with StringBuilderOptimal

TimeO(n · 4^n)SpaceO(n)

Intuition

Walk the decision tree depth-first. Level i chooses a letter for digits[i]. A single StringBuilder holds the current path: append a letter, recurse, then delete it. A string is only materialised at a leaf, so intermediate prefixes are never copied.

Algorithm

If digits is empty, return [].
dfs(i): if i == digits.length(), add sb.toString() to the result.
Otherwise, for each letter of map[digits[i]]: append, dfs(i + 1), delete the last char.

Visualization

flowchart TD
    R["'' i=0 digit 2"] -->|"a"| A["'a' i=1 digit 3"]
    R -->|"b"| B["'b' i=1"]
    R -->|"c"| C["'c' i=1"]
    A -->|"d"| A1["'ad'"]
    A -->|"e"| A2["'ae'"]
    A -->|"f"| A3["'af'"]
    B -->|"d,e,f"| B1["'bd' 'be' 'bf'"]
    C -->|"d,e,f"| C1["'cd' 'ce' 'cf'"]

Code

java

import java.util.*;

class Solution {
    private static final String[] KEYS = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result; // "" must give [], not [""]
        dfs(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void dfs(String digits, int i, StringBuilder sb, List<String> result) {
        if (i == digits.length()) {
            result.add(sb.toString());
            return;
        }
        for (char letter : KEYS[digits.charAt(i) - '0'].toCharArray()) {
            sb.append(letter);
            dfs(digits, i + 1, sb, result);
            sb.deleteCharAt(sb.length() - 1); // backtrack
        }
    }
}

Complexity

Time: O(n · 4^n) — 4^n leaves, each converted to a string in O(n).
Space: O(n) — the StringBuilder and recursion depth (output excluded).

Complexity Comparison

Approach	Time	Space (extra)
Iterative Queue	O(n · 4^n)	O(n · 4^n)
Backtracking	O(n · 4^n)	O(n)

Common Pitfalls

Returning [""] for empty input — the expected answer is [].
Forgetting that 7 and 9 have four letters, so the bound is 4^n, not 3^n.
Indexing the key array with digits.charAt(i) instead of digits.charAt(i) - '0'.
Not deleting the last character after recursion, so letters accumulate across branches.