LeetCode 17 · Medium · Backtracking

Letter Combinations of a Phone Number

Each digit from 2 to 9 maps to three or four letters, as on a phone keypad. Given a string of such digits, return every string you can spell by picking one letter per digit, in order.

O(n · 4ⁿ)time
O(n)recursion depth
one level per digitone branch per letter

0–3 digits, each 2–9 · 3 digits already grow up to 85 tree nodes

digits and their letters i points at the digit being decided · blue = letter on the current path · faded = already explored

curStr one letter per decided digit

decision tree depth i picks a letter for digits.charAt(i) · leaves are the answers

res 0 strings

private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};private List<String> res;private String digits;public List<String> letterCombinations(String digits) { res = new ArrayList<>(); this.digits = digits; if (!digits.isEmpty()) { backtrack(0, ""); } return res;}private void backtrack(int i, String curStr) { if (curStr.length() == digits.length()) { res.add(curStr); return; } for (char c : KEYS[digits.charAt(i) - '0'].toCharArray()) { backtrack(i + 1, curStr + c); }}
i
—
digits.charAt(i)
—
curStr
""
res.size()
0

Why it works

  1. Brute force needs one nested loop per digit, but the number of digits is only known at run time. Recursion is that variable number of nested loops; the iterative alternative grows a list of prefixes digit by digit.
  2. Level i decides digit i. Each call loops over the letters of digits.charAt(i) and hands a one-letter-longer string to the next level. Every root-to-leaf path picks one letter per digit, so the leaves are exactly the answers.
  3. At most 4ⁿ leaves, O(n) each. Digits 7 and 9 have four letters, the rest three. Building each string of length n costs O(n), and the depth is n.
  4. Pitfall: empty input. "" must return [], not [""]. Without the !digits.isEmpty() guard the base case fires at once and records the empty string.
  5. No undo step needed. curStr + c builds a new string, so nothing is shared between branches. With a list buffer you would append and deleteCharAt, as in Subsets.