Problem overview
The method letterCombinations receives a string digits made of the characters '2' to '9' and returns a List<String> with every word the digits could spell on a phone keypad. Each digit stands for the letters on its key (2 for abc, 3 for def, and so on up to 9 for wxyz), and a combination takes one letter per digit, 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 those starting with its second letter, and so on, with the same rule applied to each later position.
For "23" the result is [ad, ae, af, bd, be, bf, cd, ce, cf]: 3 letters times 3 letters is 9 combinations. For "7" it is [p, q, r, s], since key 7 has four letters. For the empty string the answer is an empty list, not a list holding one empty string.
Approach: choose one letter per position
With a fixed number of digits you could write nested loops, one per digit. The number of digits changes from call to call, so the loop nesting has to be generated at run time. Recursion does exactly that: each call is responsible for one position, tries every letter of that position's key, and calls itself for the next position.
This is backtracking. The search keeps current, the letters chosen so far, and an index i, the position of the digit to spell next. If i equals the number of digits, every position has a letter and current is a finished combination. Otherwise the call loops over the letters of the key for digits.charAt(i), in the key's order, and recurses with the letter appended.
The key's order gives the required output order for free. The first position changes slowest, because its loop is the outermost one, and the last position changes fastest. Run on "79" the result has 16 combinations, starting with pw, px, py, pz and ending with sz; on "234" it has 27, from adg to cfi.
Because a Java String never changes, current + letter builds a new string and leaves current as it was. Nothing has to be removed after a call returns, which is why this version has no "undo" step, unlike backtracking over a mutable list.
Step by step
- Create
resultas an emptyArrayList<String>. - Return it immediately when
digitsis empty. Without this check the search would reach its stopping condition at once and record the empty string as a combination. - Build the keypad table. A
String[]indexed by digit, with empty strings in places 0 and 1, so that every other key sits at its own index:keypad[2]is"abc",keypad[9]is"wxyz". - Start the search with position 0 and an empty
current. The helperbacktrackis assumed to exist and fillsresult. - Return
result, which now holds everything. - Write
backtrack, avoidmethod taking the digits, the positioni,current, the keypad and the result list. - Stop when
i == digits.length(). All digits are spelled. - Save
currentand return. A string can be added to the list as it is, with no copy. - Look up the letters of this digit. The character
digits.charAt(i)is something like'7'; subtracting'0'turns it into the number 7, because the digit characters are consecutive. - Loop over the letters with a for-each over
letters.toCharArray(). - Recurse with
i + 1andcurrent + letter.
The solution in Java
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) {
return result;
}
String[] keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backtrack(digits, 0, "", keypad, result);
return result;
}
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.charAt(i) - '0'];
for (char letter : letters.toCharArray()) {
backtrack(digits, i + 1, current + letter, keypad, result);
}
}
}Two language details matter here. First, digits.charAt(i) - '0' works because Java promotes both char operands to int before subtracting: '7' - '0' evaluates to 7. Second, current + letter adds a char to a String, which appends that character; it does not add numbers. If both operands were char, the sum would be an int, but here the left side is a string.
The helper has no access modifier, so it is package-private, which is fine inside the lesson's class.
Complexity
Each key has at most four letters, so n digits give at most 4^n combinations (256 for "9999", which is what a run returns). Building one takes about n steps, because each current + letter copies a string of up to n characters, so the time is O(n · 4^n). Besides the answer, the extra space is O(n): the recursion is n calls deep, each holding a string of at most n letters.
Edge cases and common mistakes
- Empty input. Without the early return,
letterCombinations("")returns a list of size 1 holding the empty string. The expected answer has size 0. - Keys 7 and 9. They have four letters, so a loop hard-coded to three letters would miss
sandz. - Using the digit character as an index.
keypad['7']would index position 55. Subtract'0'first. - Off-by-one on the table. If the table started at digit 2, every lookup would be shifted by two. The two empty strings at the front keep digit and index equal.
- Wrong order. Looping over letters in the key's order and moving to the next digit inside the loop gives keypad order. Iterating in another order, or building the result from the last digit first, changes the order of the output.
Testing
These inputs were run against the solution above:
| digits | Result |
|---|---|
"23" | [ad, ae, af, bd, be, bf, cd, ce, cf] |
"" | [] |
"7" | [p, q, r, s] |
"79" | 16 combinations, first pw, last sz |
"234" | 27 combinations, first adg, last cfi |
"9999" | 256 combinations, first wwww, last zzzz |
