题目描述
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.
Note:
The input string length won’t exceed 1000.
Example1:
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.
Example2:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
解题思路
- 这里可以用递归 Recursion 来解，需要建立一个字典，用来保存每个数字所代表的字符串，
- 然后还需要一个变量 level，记录当前生成的字符串的字符个数。
- 在递归函数中首先判断 level，如果跟 digits 中数字的个数相等了，将当前的组合加入结果 res 中，然后返回。
- 我们通过 digits 中的数字到 dict 中取出字符串，然后遍历这个取出的字符串，将每个字符都加到当前的组合后面，并调用递归函数即可，
class Solution {
public:
unordered_map<char, string> m;
vector<string> res;
vector<string> letterCombinations(string digits) {
if(digits.size() == 0){
return res;
}
m['0'] = "";
m['1'] = "";
m['2'] = "abc";
m['3'] = "def";
m['4'] = "ghi";
m['5'] = "jkl";
m['6'] = "mno";
m['7'] = "pqrs";
m['8'] = "tuv";
m['9'] = "wxyz";
dfs(digits, 0, "");
return res;
}
void dfs(string& digits, int level, string path){
if(level == digits.size()){
res.push_back(path);
return;
}
string str = m[digits[level]];
for(int i = 0; i < str.size(); i++){
dfs(digits, level + 1, path + str[i]);
}
}
};
