17 Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:
Digit string "23"
Output:
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
The Idea: First map each digit to its cooresponding alphabet. Begin with the characters to the first digit.
e.g. if d = 2
s = {"a", "b", "c"}
Next, recursively build upon this string by copying each
s[i] and appending each character cooresponding to the next digit.prev = {"a", "b", "c"}
|
next = {"ad", "ae", "af"}
prev = {"a", "b", "c"}
|
next = {"bd", "be", "bf"}
prev = {"a", "b", "c"}
|
next = {"cd", "ce", "cf"}
Complexity: O(4^n) time and O(4^n) space
const unordered_map<char, string> num_char =
{ { '2',"abc" },{ '3',"def" },
{ '4',"ghi" },{ '5',"jkl" },
{ '6',"mno" },{ '7',"pqrs" },
{ '8',"tuv" },{ '9',"wxyz" } };
void _letterCombinations(const string &digits, int iter, vector<string> &prev) {
if (iter < digits.size()) {
vector<string> next;
const string target = num_char.at(digits[iter]);
next.reserve(prev.size() * target.size());
for (int i = 0; i < prev.size(); i++) {
string build_upon = prev.at(i);
for (int j = 0; j < target.size(); j++) {
string next_str = build_upon + target.at(j);
next.push_back(next_str);
}
}
prev = next;
_letterCombinations(digits, iter + 1, prev);
}
}
string filter_digits(const string &digits) {
string filtered;
filtered.reserve(digits.size());
for (char c : digits)
if (c - '0' > 1)
filtered.push_back(c);
return filtered;
}
vector<string> letterCombinations(string digits) {
digits = filter_digits(digits);
if (digits.empty()) return vector<string>();
vector<string> result;
for (char c : num_char.at(digits[0])) {
result.push_back(string(1, c));
}
_letterCombinations(digits, 1, result);
return result;
}
Python Solution 1
This is actually a more efficient solution because I rather than completely rewriting over
prev in the previous implementation, I pass in the updated seed (which is next), and return it in the end.class Solution:
num_char = {'2': "abc", '3': "def", '4': "ghi",
'5': "jkl", '6': "mno", '7': "pqrs",
'8': "tuv", '9': "wxyz"}
def __letter_combinations(self, digits, index, seed):
"""
:type digits: str
:type iter int
:type seed List[str]
:rtype: void
"""
if index < len(digits):
target = self.num_char[digits[index]]
next = [prev + char for prev in seed for char in target]
return self.__letter_combinations(digits, index + 1, next)
else:
return seed
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
digits = ''.join(digit for digit in digits if int(digit) > 1)
if not digits:
return []
seed = [char for char in self.num_char[digits[0]]]
return self.__letter_combinations(digits, 1, seed)
#testing
obj = Solution()
result = obj.letterCombinations("239")
print(result)
Python Solution 2
Incrementally build off the base case, and just keep adding to it.
num_char = {'2': "abc", '3': "def", '4': "ghi",
'5': "jkl", '6': "mno", '7': "pqrs",
'8': "tuv", '9': "wxyz"}
class Solution:
def _letterCombinations(self, current, digit):
new_current = []
for comb in current:
for char in num_char[digit]:
new_current.append(comb+char)
return new_current
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits: return []
current = [char for char in num_char[digits[0]]]
if len(digits) == 1: return current
for digit in digits[1:]:
current = self._letterCombinations(current, digit)
return current
Last modified 4yr ago