#17 Letter Combinations of a Phone Number

frequently reported atLinkedIn Amazon Uber Microsoft Meta Google

the problem

In plain words

Given a string of digits 2–9, return every letter string they could spell on a phone keypad (2 = abc, …, 7 = pqrs, 9 = wxyz), in any order.

in digits = "23"

out ["ad","ae","af","bd","be","bf","cd","ce","cf"]

in digits = "2"

out ["a","b","c"]

1 ≤ digits.length ≤ 4
digits[i] is in '2'–'9'
Older versions also allowed an empty string (expected answer []); the code below still handles it

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking: combinations & partitions

Depth = digit index, choices = that digit's letters. No pruning needed: every leaf is an answer.

solutions

From brute force to optimal

Keep all prefixes of the current length in a queue; for each digit, replace each prefix by prefix + every letter.

queue = [""].
For each digit: poll size prefixes, offer prefix + letter for each letter.
The queue now holds all answers.

timeO(n·4ⁿ)

Up to 4ⁿ strings, each built by an O(n) concatenation.

spaceO(n·4ⁿ)

The queue holds a full level of strings.

javajava.util.*

1class Solution {2    private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};3 4    public List<String> letterCombinations(String digits) {5        if (digits.isEmpty()) return new ArrayList<>();6        Deque<String> queue = new ArrayDeque<>();7        queue.offer("");8        for (char d : digits.toCharArray()) {9            int size = queue.size();                 // all prefixes of the current length10            for (int k = 0; k < size; k++) {11                String prefix = queue.poll();12                for (char letter : KEYS[d - '0'].toCharArray()) queue.offer(prefix + letter);13            }14        }15        return new ArrayList<>(queue);16    }17}

One StringBuilder; append a letter, recurse on the next digit, delete the letter.

Empty input → [].
index == n → record path.toString().
For each letter of digit[index]: append, recurse, deleteCharAt.

timeO(n·4ⁿ)

≤ 4ⁿ leaves, each turned into a String in O(n).

spaceO(n)

Recursion depth and the builder (excluding output).

javajava.util.*

1class Solution {2    private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};3 4    public List<String> letterCombinations(String digits) {5        List<String> result = new ArrayList<>();6        if (digits.isEmpty()) return result;          // LeetCode wants [], not [""]7        backtrack(digits, 0, new StringBuilder(), result);8        return result;9    }10 11    private void backtrack(String digits, int index, StringBuilder path, List<String> result) {12        if (index == digits.length()) {13            result.add(path.toString());14            return;15        }16        for (char letter : KEYS[digits.charAt(index) - '0'].toCharArray()) {17            path.append(letter);                       // choose18            backtrack(digits, index + 1, path, result); // explore the next digit19            path.deleteCharAt(path.length() - 1);      // un-choose20        }21    }22}

in the room

How to say it in the interview

talk track

Handle the empty string first.
"Worst case 4 letters per digit (7 and 9), so 4ⁿ combinations × O(n) to build each."

traps

Returning [""] for empty input.
Using String + in the recursion: fine for n ≤ 4, but a StringBuilder shows you know the cost.

what they ask next

Follow-ups

Must the output be sorted?

It already is: each key's letters are in alphabetical order and the DFS tries them in that order, so the strings come out sorted.

Keep only strings that are real words in a dictionary?

Load the dictionary into a trie and walk it while you backtrack. If the current prefix has no trie child for a letter, skip that branch.

before you submit

Edge cases to test

One digit → its 3 or 4 letters.
7 and 9 have four letters: "7979" → 4⁴ = 256 strings, the most possible.
The same digit twice ("99") is fine: letters may repeat.

practise next