Problem overview
The method LetterCombinations receives a string digits made of the characters '2' to '9' and returns a List<string> with every word those keys could spell on a phone keypad. Key 2 carries abc, 3 carries def, and so on up to 9 with wxyz. Keys 7 and 9 have four letters, the others three. A combination takes one letter from each digit's key, in the order of the digits, and the list must be in keypad order: everything that starts with the first letter of the first key comes first, and inside each group the same rule applies to the next digit.
For "23" the result is ["ad","ae","af","bd","be","bf","cd","ce","cf"]: 3 letters times 3 letters is 9 words. For "7" it is ["p","q","r","s"]. For the empty string "" it is an empty list: nothing to spell means no combinations at all, not one empty word.
Approach: choose one letter per digit
Building the words is a decision tree. For the first digit you pick one of its letters. For each pick, you pick one letter for the second digit, and so on. A word is complete when every digit has a letter. Looping over the digits can't express this, because the number of nested loops would change with the length of the input. Recursion handles it: one call settles one digit and calls itself for the next one. This is backtracking.
A call knows the position i of the digit it must spell and the letters chosen so far, current. If i equals digits.Length, every digit has its letter, so current is a finished word and goes into the result. Otherwise the call tries each letter of the key of digits[i] in the key's order, and for each one calls itself with i + 1 and the letter added. Trying the letters in key order is what produces the keypad order.
Many backtracking solutions add a choice to a shared structure and remove it after the call. Here nothing needs removing. In C#, current + letter builds a brand-new string, so each recursive call gets its own longer word and current stays unchanged for the next letter. Strings are immutable, so a finished word can go into the result without a copy.
Step by step
- Create
result, an emptyList<string>. - Return it right away if
digits.Length == 0. Without this check the search starts ati == 0 == digits.Length, records the empty string and returns a list with one empty word. - Build the
keypadarray of ten strings, indexed by digit. Indexes 0 and 1 hold empty strings because those keys carry no letters. They are never used but keep keys 2 to 9 at their own indexes. - Call
Backtrackwithdigits, position 0, the empty string,keypadandresult, then returnresult.Backtrackfills the same list that the caller returns. - Write
Backtrack. Its base case checksi == digits.Length, addscurrenttoresultand returns. - Look up the letters of the current digit:
keypad[digits[i] - '0']. - Loop over those letters with
foreach, and for each callBacktrackwithi + 1andcurrent + letter.
The solution in C#
class Solution {
public List<string> LetterCombinations(string digits) {
List<string> result = new List<string>();
if (digits.Length == 0) {
return result;
}
string[] keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
Backtrack(digits, 0, "", keypad, result);
return result;
}
public void Backtrack(string digits, int i, string current, string[] keypad, List<string> result) {
if (i == digits.Length) {
result.Add(current);
return;
}
string letters = keypad[digits[i] - '0'];
foreach (char letter in letters) {
Backtrack(digits, i + 1, current + letter, keypad, result);
}
}
}
The C# details worth knowing:
- Converting a digit character to a number.
digits[i]is achar. The digit characters are consecutive in Unicode, so'7' - '0'is theint7, while the character'7'on its own has the numeric value 55. Usingdigits[i]directly as an index would look for position 55 and throw anIndexOutOfRangeException. - Adding a
charto a string.current + letterwith a string on the left is concatenation:"a" + 'd'is"ad". Twocharvalues added together are not concatenated. They become anint:'7' + 1is 56. foreachover a string gives its characters one at a time, aschar.- An array initializer.
string[] keypad = {"", "", "abc", ...};declares and fills the array in one statement, and the length (10) is taken from the number of values. - The helper changes the caller's list.
List<string>is a reference type, soBacktrackandLetterCombinationswork on the same list.
Complexity
Each key has at most 4 letters, so n digits give at most 4^n words. Each word is built with n concatenations, and each concatenation copies a string of up to n characters.
Time: O(n * 4^n), counting the work of building the words. With the lesson's limit of 4 digits that is at most 256 words: "7979" gives exactly 256, with "pwpw" first and "szsz" last.
Space: beyond the answer, O(n): one call per digit on the stack, each holding a string of at most n letters. The result list itself holds up to 4^n words.
Edge cases and common mistakes
- Empty input. The result must be empty. Without the length check,
""gives a list holding one empty string. - A single digit.
"7"gives the four letters of its key, each as its own string. - Repeated digits.
"22"is valid: both digits use key 2, and the result has nine words. - Using the digit character as an index. Forgetting
- '0'is the usual error, as above.
Testing
"23"gives the 9 words["ad","ae","af","bd","be","bf","cd","ce","cf"].""gives[]."7"gives["p","q","r","s"]."79"gives 16 words, from"pw"to"sz"."234"gives 27 words, from"adg"to"cfi"."7979"gives 256 words.
