Problem overview
The method letterCombinations receives digits, a string of at most four characters, each from '2' to '9'. On a phone keypad, each of those digits stands for a few letters: 2 for abc, 3 for def, and so on up to 9 for wxyz. The method returns a List<String> with every string that picks one letter for each digit, in the order of the digits.
The order of the answer matters. It is keypad order: all strings that begin with the first letter of the first key come first, and inside that group the same rule applies to the second digit, then the third. For "23" the answer is [ad, ae, af, bd, be, bf, cd, ce, cf]: nine strings, three letters for 2 times three for 3. For "7" it is [p, q, r, s], because the keys 7 and 9 have four letters.
An empty digits string has nothing to spell, and the method returns an empty list, not a list holding one empty string.
Approach: choose one letter per digit
The number of combinations is the product of the key sizes, so for n digits there are at most 4^n of them. There is no way around producing all of them. The question is how to produce them without writing one loop per digit, since the number of digits changes from input to input.
Backtracking solves that with recursion. A call handles position i of digits. It looks up the letters on that digit's key, and for each letter it calls itself for position i + 1 with the letter added to the end of the string built so far. When i reaches the length of digits, every digit has a letter, and the string is a finished combination.
Trying the letters of each key in the key's order gives keypad order for free: the first letter of the first digit stays chosen while all the later choices are explored, and only then does the first digit move to its second letter.
In the usual form of backtracking, the choice is undone after the call returns. Here nothing needs undoing: Kotlin strings never change, so current + letter builds a new string, and the caller's current is the same for the next letter.
Step by step
- Create
resultwithmutableListOf<String>(). The recursive helper adds the combinations to it. - Return
resultright away ifdigitsis empty. The search would otherwise reach the end at position 0 and record the empty string as a combination. - Build
keypad, an array of ten strings indexed by digit. Places 0 and 1 hold empty strings because those keys have no letters, which puts"abc"at index 2 and"wxyz"at index 9. - Start the search with
backtrack(digits, 0, "", keypad, result): position 0, no letters chosen yet. - Return
result, which now holds every combination, because the helper adds to the same list. - Declare
backtrackwith the digits, the positioni, the stringcurrent, the keypad and the result list. - Check for the end. When
i == digits.length, there is no digit left to spell. - Save and return. Add
currenttoresultand return. Since strings are immutable, it can be stored as it is, with no copy. - Look up the letters of the current digit with
keypad[digits[i] - '0']. - Loop over the letters of that key, in order.
- Recurse with
i + 1andcurrent + letter.
The solution in Kotlin
class Solution {
fun letterCombinations(digits: String): List<String> {
val result = mutableListOf<String>()
if (digits.isEmpty()) {
return result
}
val keypad = arrayOf("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
backtrack(digits, 0, "", keypad, result)
return result
}
fun backtrack(digits: String, i: Int, current: String, keypad: Array<String>, result: MutableList<String>) {
if (i == digits.length) {
result.add(current)
return
}
val letters = keypad[digits[i] - '0']
for (letter in letters) {
backtrack(digits, i + 1, current + letter, keypad, result)
}
}
}
Kotlin details worth knowing:
- Characters are not numbers.
digits[i]is aChar. Subtracting oneCharfrom another gives anInt:'7' - '0'is7, the digit's value. Using the character directly as an index, as inkeypad[digits[0]], does not compile:argument type mismatch: actual type is 'Char', but 'Int' was expected. The character code of'7'is 55, which is why the subtraction is needed. - A
forloop over aStringvisits its characters one by one, soletteris aChar. String + Charis allowed:current + lettercreates a newStringwith the character added at the end.- Passing the list.
resultis a reference to one list, so every recursive call adds to the same list. The return typeList<String>only hides the ability to change it from the caller. - Array type.
arrayOf("", "", "abc", ...)has the typeArray<String>, which matches the helper'skeypadparameter.
Tracing the example
For "23", the first call at position 0 tries a, b and c. Each of them calls backtrack at position 1, which tries d, e and f. Those calls are at position 2, equal to the length of digits, so they save current. In order, the saved strings are ad, ae, af, then bd, be, bf, then cd, ce, cf. Counting the first call, there are 13 calls in total: 1 at position 0, 3 at position 1 and 9 at position 2.
Complexity
Time: O(n · 4^n) for n digits. There are at most 4^n combinations, and building each one takes n steps, since every current + letter copies a string of up to n characters.
Space: O(n) besides the answer. The recursion is at most n calls deep, and each call holds a string of at most n letters.
Edge cases and common mistakes
- Empty input.
""gives[]. If the first check is left out, the search records one combination, the empty string: the list then has size 1 and holds[""]. - One digit.
"7"gives[p, q, r, s], and"2"gives[a, b, c]. - Four-letter keys.
"79"has 4 × 4 = 16 combinations, frompwtosz. The largest input,"9999", has 256 combinations, fromwwwwtozzzz. - Different key sizes.
"27"gives 3 × 4 = 12 combinations,[ap, aq, ar, as, bp, bq, br, bs, cp, cq, cr, cs].
Testing
"23"gives[ad, ae, af, bd, be, bf, cd, ce, cf].""gives an empty list."7"gives[p, q, r, s]."234"gives 27 combinations, fromadgtocfi."9999"gives 256 combinations, fromwwwwtozzzz.
