The problem. Given a string of digits from 2 to 9, return all the letter combinations the number could represent, using the letters on a phone keypad (2 = abc, 3 = def, …, 7 = pqrs, 9 = wxyz). Return them in any order; an empty input gives an empty list.
digits = "23" -> ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
digits = "" -> []
digits = "2" -> ["a", "b", "c"]This is the loop-over-choices template where the choices change at every level: level i loops over the letters of digits[i]. Every path from the top to the bottom picks one letter per digit, so every leaf is a combination. There's no pruning — every combination is valid — so the tree is the answer: up to 4 branches per level, 4ⁿ leaves.
function letterCombinations(digits) { if (digits === "") return []; const keys = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; let combos = [""]; for (const d of digits) { const next = []; for (const prefix of combos) { for (const letter of keys[d]) next.push(prefix + letter); // extend every prefix } combos = next; } return combos;}Time O(4ⁿ · n), space O(4ⁿ · n) — the breadth-first version: it keeps a whole level of partial strings in memory.
Choose a letter for the current digit, fill in the rest, then take it back and try the next letter.
function letterCombinations(digits) { if (digits === "") return []; const keys = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; const result = []; const path = []; // the letters chosen so far const choose = (i) => { if (i === digits.length) { // one letter per digit: a full combination result.push(path.join("")); return; } for (const letter of keys[digits[i]]) { path.push(letter); // choose choose(i + 1); // explore the rest path.pop(); // un-choose, to try the next letter } }; choose(0); return result;}Time O(4ⁿ · n), space O(n) besides the output: the depth-first version only ever holds one path.
[], not [""]."22": aa, ab, ac, ba, …