c++
class Solution {
private:
unordered_map<char, vector<char>> num2char {
{'2', {'a', 'b', 'c'}},
{'3', {'d', 'e', 'f'}},
{'4', {'g', 'h', 'i'}},
{'5', {'j', 'k', 'l'}},
{'6', {'m', 'n', 'o'}},
{'7', {'p', 'q', 'r', 's'}},
{'8', {'t', 'u', 'v'}},
{'9', {'w', 'x', 'y', 'z'}}
};
public:
void dfs(string &digits, int pos, string &path, vector<string> &res)
{
if (pos == digits.size())
{
res.push_back(path);
return;
}
for (auto &c: num2char[digits[pos]])
{
path.push_back(c);
dfs(digits, pos+1, path, res);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) return res;
string path = "";
dfs(digits, 0, path, res);
return res;
}
};
python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
self.dict = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
res = []
path = []
self.dfs(digits, 0, path, res)
return res
def dfs(self, digits, index, path, res):
if index == len(digits):
res.append(''.join(path))
return
for c in self.dict[digits[index]]:
path.append(c)
self.dfs(digits, index+1, path, res)
path.pop()