Letter Combinations of a Phone Number
List every letter string a phone number's digits can spell with a backtracking DFS: choose a letter, recurse, undo.
Problem Understanding
Letter Combinations of a Phone Number: given a string of digits 2–9, return every string the digits could represent on a phone keypad, where each digit maps to its letters (2 → abc, 7 → pqrs, 9 → wxyz, …).
Example: "23" returns ad, ae, af, bd, be, bf, cd, ce, cf.
The Intuition: One Choice per Digit
The answer has one position per digit, and position i can be any letter on digit i's key. That is a tree: the root branches over the first key's letters, each of those over the second key's, and so on. Every leaf is one combination.
Backtracking walks that tree with a single path:
- At position
i, append one of the key's letters. - Recurse to fill position
i + 1. - Remove the letter and try the next one.
When i reaches the number of digits, the path is complete: record it.
Interactive Walkthrough
Each digit is drawn as its phone key. The letter chosen for each position is filled and the key being filled is outlined. Recorded combinations collect beside the keys; notice the last key cycles fastest, like an odometer.
Dry Run Table
Input: "23" (2 → abc, 3 → def)
| Position 0 | Position 1 | Recorded |
|---|---|---|
| a | d, e, f | ad, ae, af |
| b | d, e, f | bd, be, bf |
| c | d, e, f | cd, ce, cf |
Nine combinations: 3 × 3.
The Solution Template
Backtracking over positions: choose a letter, recurse, undo.
Letter Combinations of a Phone Number Code
1var letterCombinations = function(digits) {2 if (!digits) return [];3 const phone = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' };4 const out = [], path = [];5 const backtrack = (i) => {6 if (i === digits.length) {7 out.push(path.join(''));8 return;9 }10 for (const ch of phone[digits[i]]) {11 path.push(ch);12 backtrack(i + 1);13 path.pop();14 }15 };16 backtrack(0);17 return out;18};
Edge Cases & Common Mistakes
- Empty input: return
[], not[""]. - Keys with four letters:
7and9have four letters each; do not assume three. - Forgetting to undo: without removing the last letter, the path keeps growing and every recorded string is wrong.
- Building strings by concatenation in the recursion: fine for 4 digits, but a single shared path with append and pop avoids copying at every level.
Summary
Each digit is one position with a few letter choices. Backtracking fills the positions in order, recording each complete path and undoing the last choice to try the next. The answer has up to 4^n strings.
More practice: DSA interview questions with answers · patterns cheat sheet