# 17. Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
Input: "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.
# Solution
Approach 1: Backtracking.
# Code (Python)
Approach 1:
def letterCombinations(self, digits: str) -> List[str]:
table = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
if '0' in digits or not digits:
return []
result = ['']
for number in digits:
new_result = []
for item in result:
for letter in table[number]:
new_result.append(item + letter)
result = new_result
return result
# Code (C++)
Approach 1:
class Solution {
private:
vector<string> letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void letterCombinations(string digits, string letterCom, vector<string>& letterComSet) {
if (digits.size() == 0)
{
if (letterCom.size() > 0)
letterComSet.push_back(letterCom);
return;
}
int digit = digits[0] - '0';
for (int i = 0; i < letters[digit].size(); ++i)
{
letterCombinations(
digits.substr(1, digits.size() - 1),
letterCom + letters[digit][i],
letterComSet);
}
}
public:
vector<string> letterCombinations(string digits) {
vector<string> letterComSet;
letterCombinations(digits, "", letterComSet);
return letterComSet;
}
};