description:
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.
telephone buttons【拼音输入法九键拿自己手机看一眼】
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
my answer:
my answer
class Solution {
public:
vector<string> letterCombinations(string digits) {
unordered_map<int, char>m = {'1':{''},
'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'},
'0':{''}};
string res = '';
vector<vector<int>> ready;
for (int i = 0; i < digits.size(); ++i){
ready.push_back(m[digits[i]]);
not finished...............from begin to give up
##############################################################
# 参考大佬的coding后恍然大悟,为什么我没有想到递归呐,因为就是
# 类似于深度优先遍历这种,从一个点扎下去然后不断地扩散,典型递
# 归的使用
##############################################################
}
}
};
大佬的answer:
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {}; //return的vector是空不是return "";是return {};
vector<string> res;
string dict[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
letterCombinationsDFS(digits, dict, 0, "", res);//这里传进去的是dict, not dict[]
return res;
}
void letterCombinationsDFS(string digits, string dict[], int level, string out, vector<string> &res) {
//这里用&res是说这个东西是引用,就是里边对res的操作会对外边的res起作用,所以返回值才是void,要不然就是vector<string>了
if (level == digits.size()) {res.push_back(out); return;}
string str = dict[digits[level] - '0'];
for (int i = 0; i < str.size(); ++i) {
letterCombinationsDFS(digits, dict, level + 1, out + string(1, str[i]), res);
}
}
};
relative point get√:
- string s(num,c) //生成一个字符串,包含num个c字符
- for (auto x : iterable something)
-
hint :