第一次做這種廣度優(yōu)先和深度優(yōu)先的題目
從昨天想到今天况既，沒想出來
看了答案理解了好久
深度優(yōu)先是一種遞歸吧棒仍，我覺得。在遞歸這方面比較薄弱莫其，我理解起來好困難乱陡。重新敲一遍的時(shí)候憨颠，也是很不熟悉。原因總結(jié)起來烙心，就是沒有深刻理解遞歸是什么淫茵，什么時(shí)候使用，怎么用铆铆，以及最后代碼怎么寫蝶缀。在最后運(yùn)行起來翁都，也可以看到和廣度優(yōu)先相比柄慰，其執(zhí)行時(shí)間和內(nèi)存消耗都比較大税娜。
廣度優(yōu)先感覺比較符合我們常規(guī)性邏輯敬矩，比較容易理解。但是其特別之處是凳忙，使用了 隊(duì)列的先進(jìn)先出（FIFO）涧卵，一起通過中間的queSize來判斷隊(duì)列的長(zhǎng)度艺演，因?yàn)殡S著后面隊(duì)列的增加，隊(duì)列長(zhǎng)度會(huì)有變化胎撤。但是其最后的執(zhí)行時(shí)間和內(nèi)存消耗都較少伤提。
法一：深度優(yōu)先
class Solution {
? ? string digits;
? ? vector<string>res;
? ? unordered_map<char,string> numStr;
public:
vector<string> letterCombinations(string digits) {
? ? ? ? //dfs
? ? ? ? this->digits = digits;
? ? ? ? if(digits.empty()){
? ? ? ? ? ? return res;
? ? ? ? }
? ? ? ? numStr =unordered_map<char,string>{{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},
? ? ? ? {'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;
}
? ? };
法二：廣度優(yōu)先
class Solution {
? ? string digits;
? ? vector<string>res;
? ? unordered_map<char,string> numStr;
public:
? ? vector<string> letterCombinations(string digits) {
this->digits = digits;
? ? ? ? if(digits.empty()){
? ? ? ? ? ? return res;
? ? ? ? }
? ? ? ? numStr =unordered_map<char,string>{{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},
? ? ? ? {'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
queue<string>queStr;
queStr.push("");
for(int i =0;i<digits.size();i++){
int queSize = queStr.size();
for(int j =0;j<queSize;j++){
string tmpStr = queStr.front();
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;
}
}
