Problem overview
letterCombinations(digits) receives a string of digits from 2 to 9 and returns every string those keys could spell on a phone keypad. The keys are: 2 has abc, 3 has def, 4 has ghi, 5 has jkl, 6 has mno, 7 has pqrs, 8 has tuv and 9 has wxyz. A combination takes one letter from each digit's key, in the order of the digits.
The combinations must come out in keypad order: all those starting with the first letter of the first key, then all those starting with its second letter, and so on, with the same rule applied to each later position. Because each key's letters are alphabetical, this is also alphabetical order. For "23" the answer is ["ad","ae","af","bd","be","bf","cd","ce","cf"]: three letters times three letters gives nine strings.
An empty digits returns an empty array, not an array holding an empty string. A single digit returns its key's letters: "7" gives ["p","q","r","s"].
Approach: choose one letter per digit
The number of results is the product of the key sizes, so there is no shortcut around producing each one. What matters is producing them in order and without a mess. Think of the answer as a decision tree. At position 0 you pick a letter of the first key, at position 1 a letter of the second key, and so on. A path from the top to the bottom, one letter per digit, is one combination.
Backtracking walks this tree depth first. A call receives the position i of the digit to spell and current, the letters chosen so far. If i equals digits.length, every digit has a letter and current is a finished combination. Otherwise the call tries each letter of the key for digits[i], in the key's order, and calls itself for the next position with that letter added.
Trying the letters in the key's order is exactly what gives the keypad order: the whole subtree under a is finished before b is tried.
In JavaScript, strings are immutable. current + letter creates a new string, so each call has its own current and nothing has to be removed after a call returns. That is the usual "undo" step of backtracking, and here it isn't needed.
Step by step
- Create
result, an empty array that collects the combinations. - Return early on empty input. If
digits.length === 0, returnresult. Without this check, the search would reach the end of the digits at once and record the empty string as a combination. - Build the
keypadarray indexed by digit: two empty strings for the digits 0 and 1, then"abc"through"wxyz"for 2 to 9. The empty entries are never used, but they keep every other key at its own index. - Start the search with
this.backtrack(digits, 0, "", keypad, result): position 0, no letters chosen. - Return
result. The helper has been adding to this same array. - Declare the helper
backtrack(digits, i, current, keypad, result)inside the class. - Check for the end: when
i === digits.length... - ...push
currentontoresultandreturn. Strings never change, so there is nothing to copy. - Look up the letters of the current digit:
keypad[Number(digits[i])].digits[i]is a one-character string such as"7", andNumberturns it into the index 7. - Loop over the letters with
for (const letter of letters). Afor...ofover a string goes through its characters one at a time. - Recurse with
i + 1andcurrent + letter.
The solution in JavaScript
class Solution {
letterCombinations(digits) {
const result = [];
if (digits.length === 0) {
return result;
}
const keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
this.backtrack(digits, 0, "", keypad, result);
return result;
}
backtrack(digits, i, current, keypad, result) {
if (i === digits.length) {
result.push(current);
return;
}
const letters = keypad[Number(digits[i])];
for (const letter of letters) {
this.backtrack(digits, i + 1, current + letter, keypad, result);
}
}
}
JavaScript details worth knowing:
- Methods call each other through
this. Inside a class method,this.backtrack(...)calls the other method of the same object. Writing justbacktrack(...)would look for a variable with that name and fail. - The array is shared, the strings are not.
resultis passed by reference, so every call pushes into the same array.currentis a string value, so each call works with its own. Number(...)is the clear way to index. An array index given as the string"2"would also find"abc", because property keys are converted to strings, but converting explicitly makes the intent obvious.- Strings and
for...of. The loop gives each character as a one-letter string, which is whatcurrent + letterneeds.
Trace on "23"
Printing i and current at the start of every call shows the depth-first order:
i=0 current=""
i=1 current="a"
i=2 current="ad"
i=2 current="ae"
i=2 current="af"
i=1 current="b"
i=2 current="bd"
i=2 current="be"
i=2 current="bf"
i=1 current="c"
i=2 current="cd"
i=2 current="ce"
i=2 current="cf"
The calls with i=2 are the finished combinations, and they appear in the order the answer needs.
Complexity
Time: O(n · 4^n) for n digits. A key has at most 4 letters, so there are at most 4^n combinations, and building each one takes n steps of string concatenation.
Extra space: O(n), besides the answer. The recursion is at most n calls deep, and each holds a string of at most n letters.
Edge cases and common mistakes
- Empty input.
""must give[]. A version without the early return gives[""], one empty combination. - One digit.
"7"gives four strings and"2"gives three, because the keys 7 and 9 have four letters and the others three. - Counting results.
"79"gives 16 combinations (4 times 4),"234"gives 27, and the largest input,"9999", gives 256. - Forgetting to move to the next digit. Passing
iinstead ofi + 1never reaches the end and recurses until the call stack overflows. - Wrong order. Looping over the letters of the key in order, with the outer choice being the earlier digit, is what produces keypad order. Making the last digit the outer choice would give
"ad","bd","cd"first, which is the wrong order. - Missing placeholders in
keypad. If the array started at"abc", the digit 2 would index the wrong entry. The two empty strings keep the indexes aligned.
Testing
"23"gives["ad","ae","af","bd","be","bf","cd","ce","cf"].""gives[]."7"gives["p","q","r","s"]."2"gives["a","b","c"]."79"gives 16 combinations, from"pw"to"sz"."9999"gives 256 combinations, from"wwww"to"zzzz".
