leetcode-电话号码的字母组合
第一次做这种广度优先和深度优先的题目
从昨天想到今天，没想出来
看了答案理解了好久
【leetcode-电话号码的字母组合】深度优先是一种递归吧，我觉得。在递归这方面比较薄弱，我理解起来好困难。重新敲一遍的时候，也是很不熟悉。原因总结起来，就是没有深刻理解递归是什么，什么时候使用，怎么用，以及最后代码怎么写。在最后运行起来，也可以看到和广度优先相比，其执行时间和内存消耗都比较大。
广度优先感觉比较符合我们常规性逻辑，比较容易理解。但是其特别之处是，使用了 队列的先进先出（FIFO），一起通过中间的queSize来判断队列的长度，因为随着后面队列的增加，队列长度会有变化。但是其最后的执行时间和内存消耗都较少。
文章图片
题目 法一：深度优先
class Solution {
string digits;
vectorres;
unordered_map
public:
vector letterCombinations(string digits) {
//dfs
this->digits = digits;
if(digits.empty()){
return res;
}
numStr =unordered_map
{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
dfs("",0);
return res;
}
void dfs(string result,int index){
int digitsSize = digits.size();
if(index == digitsSize){
res.push_back(result);
return;
}
char targetChar = digits[index];
string targetStr = numStr[targetChar];
for(auto tmpChar:targetStr){
dfs(result+tmpChar,index+1);
}
return;
}
};
法二：广度优先
class Solution {
string digits;
vectorres;
unordered_map
public:
vector letterCombinations(string digits) {
this->digits = digits;
if(digits.empty()){
return res;
}
numStr =unordered_map
{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
queuequeStr;
queStr.push("");
for(int i =0;
i
for(int j =0;
j
queStr.pop();
char tmpChar = digits[i];
string targetStr = numStr[tmpChar];
for(auto tmpC:targetStr){
queStr.push(tmpStr+tmpC);
}
}
}
while(!queStr.empty()){
string tmp = queStr.front();
queStr.pop();
res.push_back(tmp);
}
return res;
}
}
文章图片
题解记录
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量