解法框架

【README】回溯算法基本框架

電話號碼的組合(點擊跳轉(zhuǎn))

對于這道題，很明顯涉及到的也是回溯算法。但是這道題有一特別之處，就是它的選擇列表給的不明顯，回想全排列那道題目，其選擇列表給出的十分明顯。此題之中則是多了一層映射關(guān)系，所以必須有一個類似于哈希表的結(jié)構(gòu)保存這種映射關(guān)系，這里直接使用vector即可

vector<string> map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//選擇列表

首先，這道題的形參是一個字符串，這個字符串中有若干數(shù)字字符，每個字符都對應(yīng)了相應(yīng)的字母列表，函數(shù)的返回值是一個一維數(shù)組，數(shù)組的每個元素是一個字符串，字符串里保存的是滿足條件的組合

因此擺出，回溯算法基本框架

接下來編寫遞歸函數(shù)back，路徑肯定是track，但是選擇列表呢？是選擇digits呢還是map呢，其實這也是本題的一個難點。以“23”為例，其決策樹如下

可以發(fā)現(xiàn)這種對應(yīng)關(guān)系有些“奇怪”，讓人很難受，它并不是單純的對應(yīng)，其難受點就在于這個數(shù)字和字母的對應(yīng)上。比如當處理2時，第一個加入路徑的是a，然后此時下一個應(yīng)該選擇d，但是問題就在這里，d對應(yīng)的是數(shù)字3，已經(jīng)不是2的范疇了。所以這個選擇列表應(yīng)該有兩部分組成，一個是digits，一個是index，index用于控制數(shù)字。每次進入遞歸時，根據(jù)index拿到數(shù)字，然后根據(jù)數(shù)字在map中找到對應(yīng)的字母列表，然后開始選擇操作。

class Solution { public:vector<string> ret;//返回結(jié)果vector<string> map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//選擇列表vector<string> letterCombinations(string digits) {string track;//路徑if(digits.size()==0)//特殊情況{return ret;}back(track,digits,0);return ret;}void back(string track,string digits,int index)//遍歷決策樹{if(track.size()==digits.size())//一條路徑已經(jīng)走完，可以加上這種情況{ret.push_back(track);return;}int pos=digits[index]-'0';//根據(jù)index拿出數(shù)字，所以pos就決定了要選擇哪個按鍵上的字母string temp=map[pos];//temp里保存的就是字母for(int i=0;i<temp.size();i++)//遍歷選擇列表{ track.push_back(temp[i]);//做出選擇back(track,digits,index+1);//遍歷決策樹，index肯定要加1，因為//一個按鍵上只能選擇一個字母track.pop_back();//撤銷選擇}} };

所以這道題相較于全排列來說就多了一層映射關(guān)系。在全排列時我們選擇數(shù)字不能出現(xiàn)重復(fù)，其實這里也是一樣，我們選擇字母不能第一次和第二次都在一個按鍵上選擇字母

總結(jié)

以上是生活随笔為你收集整理的回溯算法之电话号码的字母组合的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。