Problem
Given a string digits containing digits from2 to 9, return all possible letter combinations that the number could represent.
Each digit maps to a set of letters, similar to the keys on a traditional phone keypad. The order of the combinations does not matter.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
digits = "23"Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]Example 2
Input
digits = ""Output
[]Solution
This solution uses the Backtracking pattern. We build the combination one digit at a time and try every letter mapped to the current digit.When we have processed all digits, the current combination is complete, so we add it to the result. After exploring one letter, we remove it and try the next letter.
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.length() == 0) {
return result;
}
String[] letters = {
"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"
};
backtrack(digits, 0, "", letters, result);
return result;
}
private void backtrack(String digits, int i, String current,
String[] letters, List<String> result) {
// All digits have been processed.
if (i == digits.length()) {
result.add(current);
return;
}
String chars = letters[digits.charAt(i) - '0'];
// Try every letter mapped to the current digit.
for (char c : chars.toCharArray()) {
backtrack(digits, i + 1, current + c, letters, result);
}
}
}Complexity
Each digit can have up to 4 possible letters, so there can be up to4n combinations. Since each combination contains n characters, the time complexity is O(4n × n).
The recursion uses
O(n) stack space, excluding the space required to store the generated combinations. Including the output, the space complexity is O(4n × n).