LintCode 425. Letter Combinations of a Phone Number
很有意思的一道題。DFS經典使用
DFS几个要素:
1,写入最终结果的条件
2, 黑盒子什么功能
3, 带入黑盒子的参数。
class Solution {
public:
/**
* @param digits: A digital string
* @return: all posible letter combinations
*/
const vector<string> letters {"", "","abc","def", // '0','1','2',...
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 语法1
vector<string> letterCombinations(string &digits) {
// write your code here
// DFS
vector<string> res;
int sizeD = digits.size();
if(sizeD == 0){
return res;
}
dfs(digits, res, 0, "");
return res;
}
void dfs(string &digits, vector<string> &res, int cur, string path){
if(cur == digits.size()){
res.push_back(path);
return;
}
for(auto elem : letters[digits[cur] - '0']){ //语法2
dfs(digits, res, cur + 1, path + elem);
}
}
};
二刷2019年03月24日21:07:58
const vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> letterCombinations(string &digits) { // write your code here const int size = digits.size(); vector<string> res; if(size == 0){ return res; } string resElem; dfs(digits, res, resElem, 0); return res; } void dfs(string &digits, vector<string> &res, string resElem, int cur){ if(resElem.size() == digits.size()){ res.push_back(resElem); } for(int i = 0; i < mapping[digits[cur] - '0'].size(); i++){ dfs(digits, res, resElem + mapping[digits[cur] - '0'][i], cur + 1); } }
DFS几个要素:
1,写入最终结果的条件
2, 黑盒子什么功能
3, 带入黑盒子的参数。
class Solution {
public:
/**
* @param digits: A digital string
* @return: all posible letter combinations
*/
const vector<string> letters {"", "","abc","def", // '0','1','2',...
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 语法1
vector<string> letterCombinations(string &digits) {
// write your code here
// DFS
vector<string> res;
int sizeD = digits.size();
if(sizeD == 0){
return res;
}
dfs(digits, res, 0, "");
return res;
}
void dfs(string &digits, vector<string> &res, int cur, string path){
if(cur == digits.size()){
res.push_back(path);
return;
}
for(auto elem : letters[digits[cur] - '0']){ //语法2
dfs(digits, res, cur + 1, path + elem);
}
}
};
二刷2019年03月24日21:07:58
const vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> letterCombinations(string &digits) { // write your code here const int size = digits.size(); vector<string> res; if(size == 0){ return res; } string resElem; dfs(digits, res, resElem, 0); return res; } void dfs(string &digits, vector<string> &res, string resElem, int cur){ if(resElem.size() == digits.size()){ res.push_back(resElem); } for(int i = 0; i < mapping[digits[cur] - '0'].size(); i++){ dfs(digits, res, resElem + mapping[digits[cur] - '0'][i], cur + 1); } }
Comments
Post a Comment