
Description
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Intuition
Each digit corresponds to a set of letters. The problem is essentially about generating all combinations of these letters corresponding to the sequence of digits provided. This is a classic example of a combinatorial problem which can be solved using backtracking.
Approach
- Mapping: Create a dictionary to map each digit to its respective letters.
- Backtracking: Use a helper function to generate combinations. Start with an empty string and iterate through the digits. - For each digit, append each possible letter to the current combination and recurse for the next digit. - If the current combination has a length equal to the number of digits, add it to the results list.
- Base Case: If the input digits string is empty, immediately return an empty list.
Complexity
Time Complexity:
(O(3^N \times 4^M)), where (N) is the number of digits that maps to 3 letters (like 2, 3, 4, 5, 6, 8) and (M) is the number of digits that maps to 4 letters (like 7, 9). This is because there are 3 possibilities for each of the (N) digits and 4 possibilities for each of the (M) digits.
Space Complexity:
(O(3^N \times 4^M)) for the output list, plus the recursion stack.
Code
C++
class Solution {
public:
vector letterCombinations(string digits) {
if (digits.empty()) return {};
unordered_map keyboard = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}
};
vector output;
function backtrack = [&](string current, int index) {
if (index == digits.size()) {
output.push_back(current);
return;
}
string letters = keyboard[digits[index]];
for (char letter : letters) {
backtrack(current + letter, index + 1);
}
};
backtrack("", 0);
return output;
}
};
Python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
keyboard = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
output = []
def backtrack(current, index):
if index == len(digits):
output.append(current)
return
letters = keyboard[digits[index]]
for letter in letters:
backtrack(current + letter, index + 1)
backtrack("", 0)
return output
Java
class Solution {
public List letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
Map keyboard = new HashMap<>();
keyboard.put('2', "abc");
keyboard.put('3', "def");
keyboard.put('4', "ghi");
keyboard.put('5', "jkl");
keyboard.put('6', "mno");
keyboard.put('7', "pqrs");
keyboard.put('8', "tuv");
keyboard.put('9', "wxyz");
List output = new ArrayList<>();
backtrack(output, keyboard, digits, "", 0);
return output;
}
private void backtrack(List output, Map keyboard, String digits, String current, int index) {
if (index == digits.length()) {
output.add(current);
return;
}
String letters = keyboard.get(digits.charAt(index));
for (char letter : letters.toCharArray()) {
backtrack(output, keyboard, digits, current + letter, index + 1);
}
}
}
JavaScript
var letterCombinations = function (digits) {
if (digits.length === 0) return [];
const keyboard = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
};
const output = [];
const backtrack = (current, index) => {
if (index === digits.length) {
output.push(current);
return;}
const letters = keyboard[digits[index]];
for (let letter of letters) {
backtrack(current + letter, index + 1);}
};
backtrack('', 0);
return output;
};