今天 leetcode 寫了一道題湃交，它既可以用深度優(yōu)先搜索籍救，也可以用廣度優(yōu)先搜索來解決，不妨一起來看看吧蝎土！
題目描述
給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合绣否。
給出數(shù)字到字母的映射如下（與電話按鍵相同）誊涯。注意 1 不對應任何字母。
示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說明:
盡管上面的答案是按字典序排列的蒜撮，但是你可以任意選擇答案輸出的順序暴构。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
下面，我們將分別使用 DFS 和 BFS 來解決該問題段磨。
深度優(yōu)先搜索(DFS)
Depth-First-Search：深度優(yōu)先搜索丹壕，它沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分 支薇溃。當節(jié)點的所有邊都己被訪問過菌赖，搜索將回溯到原節(jié)點邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從原節(jié)點可達的所有節(jié)點為止沐序。如果存在未被訪問的節(jié)點琉用，則選擇其中一個作為節(jié)點并重復以上過程，整個進程反復進行直到所有節(jié)點都被訪問為止策幼。
打個不恰當?shù)谋确揭厥保汩_車去一個地方，但是路上分叉路多特姐，你又沒地圖晶丘，那只能把每個分叉路走都走一遍，走到頭也沒到唐含，返回之前路口再走浅浮，最多把所有的子路徑都走一遍就能到達目的地。
下面捷枯，我們來看看如何利用 DFS 來解決這個問題滚秩。
以一個例子來看，"237"淮捆。
這是一個示意圖郁油，用畫布畫的本股，有些丑。桐腌。拄显。
簡單模擬下這個過程
先從 '2' 的一個節(jié)點 a 出發(fā)，發(fā)現(xiàn)還能往下走案站，就來到了 '3' 的一個節(jié)點 d 躬审，發(fā)現(xiàn)還可以繼續(xù)往下走，就來到了 '7' 的一個節(jié)點 p嚼吞，這個時候再往下走就不行了，此時我們把 "adp" 存起來蹬碧。
由于已經(jīng)無路可走了舱禽，只能返回之前的節(jié)點，再往下走恩沽，來到 q ,再往下走誊稚，無路可走了，把 "adq" 存起來罗心。
重復上面的過程里伯。
那么終止條件是什么呢？當然是"層數(shù)"了
圖示過程：
程序如下：
class Solution {
public:
vector<string> res;
unordered_map<char,string> store;
vector<string> letterCombinations(string digits) {
if(digits.empty()){
return res;
}
store = {
{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"}, {'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"} , {'9',"wxyz"}};
dfs("", 0,digits);
return res;
}
void dfs(string str,int index,string digits){
int len=digits.size();
if(len==index){
res.push_back(str);
return ;
}
string targerStr=store[digits[index]];
for(auto temp : targerStr){
dfs(str+temp,index+1,digits);
}
return ;
}
};
廣度優(yōu)先搜索(BFS)
BFS是從根節(jié)點開始渤闷，沿著樹(圖)的寬度遍歷樹(圖)的節(jié)點疾瓮。如果所有節(jié)點均被訪問，則算法中止飒箭。
簡單模擬下這個過程：
先把根節(jié)點入隊列：
再找下一個未被訪問的節(jié)點：
當然我們不能簡單地把 "def" “塞進去”狼电，"def" 進去后的結(jié)果應該是其與隊列中所有成員的組合。
這個過程可以這樣操作：
隊列中所有元素都分別加上當前節(jié)點的所有元素弦蹂。
之后重復這樣的操作：
程序如下：
class Solution {
public:
vector<string> res;
unordered_map<char,string> store;
vector<string> letterCombinations(string digits) {
if(digits.empty()){
return res;
}
store = {{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"}, {'6',"mno"},{'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}};
queue<string> q;
q.push("");
for(auto temp : digits){
string targetStr=store[temp];
int qSize=q.size();
//位于當前層肩碟，添加字符
for(int i=0;i<qSize;i++){
string tempStr=q.front();
q.pop();
for(auto tmp : targetStr){
q.push(tempStr+tmp);
}
}
}
while(q.size()!=0){
string tempStr=q.front();
q.pop();
res.push_back(tempStr);
}
return res;
}
};
這個題使用深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)都可以解決，下面我們匯總兩個程序凸椿。
匯總
把這個兩個程序匯總削祈，更方便我們測試，整理如下：
#include <bits/stdc++.h>
using namespace std;
class DFS_{
public:
vector<string> res;
string digits;
unordered_map<char, string> store;
vector<string> letterCombinations(){
this->digits = digits;
if (digits.empty()){
return res;
}
store = 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 resultStr, int index){
int digitsSize = this->digits.size();
if (digitsSize == index){
res.push_back(resultStr);
return ;
}
string targetStr = store[this->digits[index]];
for (auto tmpChar : targetStr){
dfs(resultStr + tmpChar, index + 1);
}
return ;
}
};
class BFS_{
public:
vector<string> res;
string digits;
unordered_map<char, string> store;
vector<string> letterCombinations(){
this->digits = digits;
if(digits.empty()){
return res;
}
store = {{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"}, {'6',"mno"},{'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}};
queue<string> q;
q.push("");
for(auto temp : digits){
string targetStr=store[temp];
int qSize=q.size();
//位于當前層脑漫，添加字符
for(int i=0;i<qSize;i++){
string tempStr=q.front();
q.pop();
for(auto tmp : targetStr){
q.push(tempStr+tmp);
}
}
}
while(q.size()!=0){
string tempStr=q.front();
q.pop();
res.push_back(tempStr);
}
return res;
}
};
int main(){
string str;
cin>>str;
DFS_ d;
BFS_ b;
d.digits=str;
b.digits=str;
vector<string> res_d = d.letterCombinations();
cout<<"DFS: "<<endl;
for(auto& temp : res_d){
cout<<temp<<" ";
}
cout<<endl;
cout<<"BFS: "<<endl;
vector<string> res_b = b.letterCombinations();
for(auto& temp : res_b){
cout<<temp<<" ";
}
cout<<endl;
return 0;
}
示例如下：
雖然 DFS 和 BFS 的理論不難理解髓抑，實際應用過程中還是需要多加練習，才能很好地掌握优幸。
