Dare2Solve
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.
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.
(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.
(O(3^N \times 4^M)) for the output list, plus the recursion stack.
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
unordered_map<char, string> keyboard = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}
};
vector<string> output;
function<void(string, int)> 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;
}
};
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
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
Map<Character, String> 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<String> output = new ArrayList<>();
backtrack(output, keyboard, digits, "", 0);
return output;
}
private void backtrack(List<String> output, Map<Character, String> 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);
}
}
}
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;
};