Problem 13.5 · BacktrackingMedium

Letter Combinations of a Phone Number

What it teaches: One decision per position, with the options given by a lookup table: a product of choices.

Practise it on judges as “Letter Combinations of a Phone Number”.

The problem

Given a string of digits 2–9, return all letter combinations they could represent on a phone keypad (2 → abc, 3 → def, ..., 7 → pqrs, 9 → wxyz). Return an empty list for an empty input.

Example 1

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

Example 2

Input: digits = ""
Output: []

Constraints

0 ≤ digits.length ≤ 4

Pattern clues in the wording

→ One choice per position from a fixed set
→ "All combinations"

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<String> letterCombinations(String digits) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	digits = "23"	["ad","ae","af","bd","be","bf","cd","ce","cf"]
2	digits = ""	[]
3	digits = "2"	["a","b","c"]

From slow to fast

Approaches

1. Backtracking over positions · O(4ⁿ · n)

Backtracking over positions

Time O(4ⁿ · n) Space O(n)

dfs(index): if index == length record; else for each letter of digits[index], append, recurse, remove.

Approach 1

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> out = new ArrayList<>();
        if (digits.isEmpty()) return out;
        dfs(digits, 0, new StringBuilder(), out);
        return out;
    }

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

Verdict: At most 4⁴ = 256 results.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty input → []
Digits 7 and 9 (four letters)

Mistakes people make

Returning [""] for empty input.

Interview

Follow-up questions

Can you do it iteratively?

Command Palette

The problem

Approaches

Backtracking over positions

Edge cases and common mistakes

Follow-up questions