題目描述

解題思路：

這是一個(gè)深度優(yōu)先遍歷的題目，涉及到多路遞歸，下面通過畫圖和解析來分析這道題。

首先說到的是映射關(guān)系，那么我們就可以通過一個(gè)字符串?dāng)?shù)組來表示映射關(guān)系（字符串下標(biāo)訪問對應(yīng)著數(shù)字映射到對應(yīng)的字符串）比如我們輸入的是‘2’，那么通過A[2]就可以得到對應(yīng)的字符串“abc”

string A[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

我們可以將數(shù)字對應(yīng)的字符串進(jìn)行分層，然后通過遞歸來實(shí)現(xiàn)深度遍歷，for循環(huán)來實(shí)現(xiàn)廣度遍歷，從而得到對應(yīng)的組合。最后將排列組合用vector<string>&類型容器存儲起來。

這題我們就拿“246”來舉例，我們用level來表示層數(shù)，將映射出的字符串劃分為0 1 2層，先進(jìn)行深度遍歷，一層一層的將單個(gè)字符進(jìn)行拼接(注意這里拼接得到的字符串str不能使用引用，因?yàn)樯疃缺闅v完一層之后，進(jìn)行另外一層遍歷我們是不希望受到前面遍歷的影響的)比如第一次深度遍歷得到“agm”，如果是使用引用傳參，那么在第一次遍歷之后，str就變成了“agm”在后續(xù)遍歷中不方便操作。

當(dāng)level達(dá)到所給數(shù)字字符串的size的時(shí)候也就是level==3時(shí)，將得到的字符串str加到vector<string> v里邊這里的類型得用引用。

    void combine(string digits,int level,string str,vector<string>& v){if(level==digits.size()){v.push_back(str);return;}int num=digits[level]-'0';string s=A[num];for(int i=0;i<s.size();i++){combine(digits,level+1,str+s[i],v);}}

下面通過畫圖來演示一下遞歸流程：

完整代碼如下：

class Solution {
public:string A[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//與輸入的數(shù)字字符形成映射關(guān)系void combine(string digits,int level,string str,vector<string>& v){     if(level==digits.size()){v.push_back(str);return;}int num=digits[level]-'0';string s=A[num];for(int i=0;i<s.size();i++){combine(digits,level+1,str+s[i],v);}}vector<string> letterCombinations(string digits) {vector<string> v;if(digits=="")//如果是空串，直接返回空的對象v{return v;}combine(digits,0,"",v);//從第0層開始，str為空串return v;}
};

?