Problem overview
The method letterCombinations receives digits, a string of digits from 2 to 9, and returns every string those digits could spell on a phone keypad. Each digit stands for the letters on its key: 2 is abc, 3 is def, 4 is ghi, 5 is jkl, 6 is mno, 7 is pqrs, 8 is tuv and 9 is wxyz. A combination takes one letter from each key, in the order of the digits.
The combinations must come 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 inside each group for the next digit. Because each key's letters are alphabetical, this is alphabetical order. For "23" the answer is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]: three letters times three letters gives nine strings. For "7" it is ["p", "q", "r", "s"]. For an empty string it is [], an empty array, and not an array holding one empty string.
The string has at most 4 digits.
Approach: choose one letter per digit, recursively
The answer is a product of choices: one letter for the first digit, one for the second, and so on. The number of nested loops would depend on the number of digits, which is not known in advance, so a recursive function takes the place of the loops.
That function is called backtrack. It handles one position i of digits and carries current, the letters chosen so far. If i equals the length of digits, every digit has a letter, and current is a finished combination to save. Otherwise it looks up the letters of digits[i] and, for each letter in the key's order, calls itself for position i + 1 with that letter added to the end of current.
Trying letters in the key's order gives keypad order for free. The first call goes deep with the first letter of every key before anything else changes, and the last digit's letter changes fastest, exactly as in the "23" list above.
This is backtracking: build a partial answer, extend it in every possible way, and fall back to try the next option. The usual detail is undoing a choice after the recursive call returns. Here nothing needs undoing, because strings are immutable: current + letter creates a new string and leaves current untouched for the next letter of the loop.
Step by step
- Create
resultas an emptystring[]to collect the combinations. - Return
resultfor an emptydigits. Without this check, the search would reach the end at once and save the empty string, giving[""]instead of[]. - Build
keypad, an array indexed by digit. Positions 0 and 1 hold empty strings because those keys have no letters, which keeps 2 to 9 at their own indices. - Start the search with position 0 and an empty
current, passingkeypadandresultalong. - Return
result, which the search filled in place. - Write the helper
backtrackinside the class, with the parametersdigits,i,current,keypadandresult, returningvoid. - Check for the end: if
i === digits.length, every digit has its letter. - Save and return. Push
currentontoresultas it is, since a string can't change later, thenreturn. - Look up the letters of the current digit:
digits[i]is a one-character string such as"7", andNumberturns it into 7, the index of its key. - Loop over the letters with
for...of, which goes through a string one character at a time. - Recurse with
i + 1andcurrent + letter.
The solution in TypeScript
class Solution {
letterCombinations(digits: string): string[] {
const result: string[] = [];
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: string, i: number, current: string, keypad: string[], result: string[]): void {
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);
}
}
}
Some TypeScript details:
- Calling a method from a method. Inside a class,
backtrackmust be called asthis.backtrack(...). A barebacktrack(...)looks for a function outside the class and is reported as an error. - Sharing
result. Arrays are passed by reference, so every call pushes into the same array thatletterCombinationsreturns. No call needs to return anything, which is whybacktrackis typedvoid. for...ofover a string. It visits characters, not indexes. Usefor...inby mistake andletterbecomes the index"0","1", and so on.- Digits as characters.
digits[i]has typestring, and the type is erased at run time just like every annotation.Number(digits[i])really converts:Number("7")is the number 7.
Complexity
Time: O(n · 4^n). A key has at most 4 letters, so n digits give at most 4^n combinations (exactly 3^n when no digit is 7 or 9). Building one combination copies up to n characters through the string concatenations. For "9999" the result has 256 strings, which is 4^4.
Space: O(n) besides the answer. The recursion is n calls deep, one per digit, and each call holds a string of up to n letters. The answer itself takes O(n · 4^n).
Edge cases and common mistakes
- Empty input.
""returns[]. Remove the early return and the same input returns[""], an array with one empty string. - One digit.
"2"gives["a", "b", "c"]and"7"gives four letters. The search needs no special case. - Counting results.
"27"gives 3 × 4 = 12 combinations, from"ap"to"cs", and"79"gives 16. - Wrong key index. The keypad array starts with two empty entries. Without them,
keypad[2]would be the letters of the wrong key. A keypad of just["abc", "def"]would turnkeypad[Number("2")]intoundefined, and looping over it would throw. - Digits 0 and 1. They don't occur in the input. If
1did appear, its empty key would make the loop run zero times, and the whole input would return[]. - Mutating a shared string builder. If you build
currentas an array and push into it, you must pop after each call. With strings, the concatenation does that work for you.
Testing
"23"gives["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].""gives[]."7"gives["p", "q", "r", "s"]."2"gives["a", "b", "c"]."27"gives 12 strings, starting"ap","aq","ar","as","bp"."9999"gives 256 strings, from"wwww"to"zzzz".
