Problem overview
The function letter_combinations receives digits, a String made of the digits 2 to 9. On a phone keypad each of those digits stands for a few letters: 2 is abc, 3 is def, and so on up to 9, which is wxyz. The function returns every string that picks one letter for each digit, in the order of the digits, as a Vec<String>.
The combinations must come in keypad order: all those that start with the first letter of the first key come before those that start with its second letter, and the same rule applies inside each group. For "23" the answer is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]: three letters for the 2, three for the 3, 3 × 3 = 9 combinations. With the single digit "7" the result is ["p", "q", "r", "s"], because the 7 key has four letters. An empty digits returns an empty vector, not a vector holding one empty string.
Approach: choose one letter per digit
The number of combinations is the product of the key sizes, so there is no shortcut around producing every one of them. The task is to produce them systematically, with no repeats and in the right order.
Backtracking does this by walking through digits one position at a time and keeping the letters chosen so far in a string, current. At position i, the function tries each letter of the key for digits[i], in the key's order. For each letter it builds a longer string and moves on to position i + 1. When the position reaches the end of digits, every digit has its letter, and current is a full combination to save.
Because the letters of a key are tried in order, and the outermost position changes slowest, the combinations come out in exactly the order the task asks for. For "23" the calls happen like this:
backtrack(i = 0, current = "")
backtrack(i = 1, current = "a")
backtrack(i = 2, current = "ad")
backtrack(i = 2, current = "ae")
backtrack(i = 2, current = "af")
backtrack(i = 1, current = "b")
backtrack(i = 2, current = "bd")
backtrack(i = 2, current = "be")
backtrack(i = 2, current = "bf")
backtrack(i = 1, current = "c")
backtrack(i = 2, current = "cd")
backtrack(i = 2, current = "ce")
backtrack(i = 2, current = "cf")
The calls at i = 2 are the ones that save a result. Every call passes down its own, longer string, so nothing has to be undone when a call returns: the shorter current in the caller is untouched.
Step by step
- Create
resultas an empty vector withVec::new(). Rust infersVec<String>from the return type. - Return early on empty input. With no digits, the search would reach the end at once and save the empty string. The task wants no combinations at all, so the function returns the empty
resultfirst. - Build the
keypadarray of string slices, indexed by digit: two empty strings for the keys 0 and 1, then"abc"up to"wxyz". The empty places never get used, but they keep every other key at its own index. - Start the search with
Self::backtrack, giving it the digits as bytes, position 0, an emptyString, the keypad, and a mutable borrow ofresult. - Return
resultas the last expression. - Declare the helper
backtrackinside the sameimpl. It takes the digits as&[u8], the positioni, the letters chosen so far, the keypad as&[&str]andresultas&mut Vec<String>. - Check for the end. When
i == digits.len(), every digit has a letter. - Save and return. Push
currentontoresultand return. The string is moved into the vector, so no copy is made. - Look up the letters of the current digit:
digits[i] - b'0'turns the byte of a digit character into its number, andas usizemakes it an index into the keypad. - Loop over the letters of that key with
letters.chars(), in order. - Recurse with
i + 1andformat!("{}{}", current, letter), which builds a new string with the letter added at the end.
The solution in Rust
impl Solution {
fn letter_combinations(digits: String) -> Vec<String> {
let mut result = Vec::new();
if digits.is_empty() {
return result;
}
let keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
Self::backtrack(digits.as_bytes(), 0, String::new(), &keypad, &mut result);
result
}
fn backtrack(digits: &[u8], i: usize, current: String, keypad: &[&str], result: &mut Vec<String>) {
if i == digits.len() {
result.push(current);
return;
}
let letters = keypad[(digits[i] - b'0') as usize];
for letter in letters.chars() {
Self::backtrack(digits, i + 1, format!("{}{}", current, letter), keypad, result);
}
}
}
The Rust details worth a closer look:
- No indexing a
String. Rust strings are UTF-8 text, anddigits[i]does not compile for aString.as_bytes()gives a&[u8]that can be indexed by position. That is fine here, because every digit character is a single byte. - Byte arithmetic.
b'0'is the byte value of the character'0'. The digit characters are consecutive, sob'7' - b'0'is the number 7. - Borrowing.
&keypadturns the array into a slice&[&str]without copying it.&mut resultlends the vector mutably, and inside the recursionresultis passed on as it is, because it already is a&mutreference. - Ownership of
current. The parameter is aStringtaken by value. Pushing it ontoresultmoves it, which is why noclone()is needed. Each recursive call gets a new string fromformat!, so the loop can keep using this call'scurrentfor the next letter. chars(). It yieldscharvalues, andformat!with{}prints acharas the letter itself.- Final expression.
resulthas no semicolon, so it is what the function returns.
Complexity
Time: O(n * 4^n) for n digits. A key has at most four letters, so there are at most 4^n combinations, and building each one takes about n steps because every call creates a string of up to n letters.
Space: O(n) beyond the answer. There is one active call per digit, and each holds a string of at most n letters. The answer itself holds 4^n strings in the worst case.
Edge cases and common mistakes
- Empty input. Without the early return the function gives
[""], a vector with one empty string, instead of[]. - Keys with four letters. The digits 7 and 9 have four letters.
"79"gives 4 × 4 = 16 combinations, from"pw"to"sz". - A keypad without the two empty places. If the array starts at
"abc", every lookup is off by two: the digit 2 would spellg,h,i, and the digit 9 would index past the end and panic with an out-of-bounds error. - Indexing with the character. The byte of
'7'is not 7. Subtractingb'0'is what gives the key number. - Wrong order. The result follows from trying each key's letters in order. Looping over the letters in any other order changes the output order, and the lesson's tests expect keypad order.
- Four digits at most. The longest input, such as
"7979"or"9999", gives 256 combinations, so the recursion is shallow and the output is small.
Testing
"23"gives the nine strings["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].""gives[]."7"gives["p", "q", "r", "s"]."79"gives 16 strings, from"pw"to"sz"."234"gives 27 strings, from"adg"to"cfi"."7979"gives 256 strings, from"pwpw"to"szsz".
