在我們的座機(jī)上，都有這種數(shù)字與字母對應(yīng)的按鍵。

以此為例，講解多叉樹的深度優(yōu)先遍歷

問題

給定一個僅包含數(shù)字?2-9?的字符串，返回所有它能表示的字母組合。答案可以按?任意順序?返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = ""
輸出：[]

示例 3：

輸入：digits = "2"
輸出：["a","b","c"]

• 0 <= digits.length <= 4
• digits[i]?是范圍?['2', '9']?的一個數(shù)字。

分析

假設(shè)我們輸入的是 2 5 8 那么對應(yīng)元素分別是abc jkl tuv。一共有3*3*3 = 27鐘組合。我們的思路是

先從2中取a，再從5中取j，再從8中取t。將三個字母存放到一個字符串中。再將不斷組合好的字符串push_back到vector<string>中

完成好一組之后，到達(dá)最深再返回，再組合a j u；再push_back。

代碼

class Solution {
private:const char* numStrArr[10]= {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};   //存放字符串的數(shù)組public:void Combine(const string& digits, int i, string combineStr,vector<string>& ret){if (i == digits.size())     //深度遍歷{ret.push_back(combineStr);return;}int num = digits[i] - '0';string str =numStrArr[num];    //數(shù)字映射的字母for (auto ch : str)     //取一個字符，去排列組合{Combine(digits,i+1,combineStr+ch,ret);}}vector<string> letterCombinations(string digits) {vector<string> v;   //存放字符串組合string str; if (digits.empty())return v;Combine(digits,0, str,v);return v;}
};

幾個對象的功能digits,0, str,v

digits：存儲輸入的字符串

0：作為下標(biāo)，不斷遍歷字符串，知道到達(dá)size()為止

str：將映射好的數(shù)據(jù)存儲到str中

v:返回數(shù)組

核心代碼

string str =numStrArr[num]; ? ?//數(shù)字映射的字母

? ? ? ? for (auto ch : str) ? ? //取一個字符，去排列組合

? ? ? ? {

? ? ? ? ? ? Combine(digits,i+1,combineStr+ch,ret);

? ? ? ? }

假設(shè)還是 2 5 8 。取到2的首字母之后，進(jìn)入遞歸，取5的首字母。繼續(xù)遞歸取到8的首字母。

再push_back

回到循環(huán)，繼續(xù)取8的第二個字母

等到5的首字母取完之后，再取5的第二個字母，繼續(xù)遞歸。

剖解代碼

通過上述的分析，我們可以得出，

1.需要靠一個遞歸完成遍歷。遞歸的返回條件是深度達(dá)到size（）

2.既然是數(shù)字與字母的映射，那就需要借助下標(biāo)去不斷遍歷讀取到的字符串?

3.在不斷加深的過程中，應(yīng)該靠的是 + 而不是+=，這樣return之后，就可以回到原來的字符串

經(jīng)驗總結(jié)

當(dāng)我們直接上手，可能不會那么容易。但是顯然的是，這是存放在容器中的數(shù)據(jù)。因此理所應(yīng)到要去考慮到用什么類型的數(shù)據(jù)結(jié)構(gòu)去存放數(shù)據(jù)。從而想到該用什么方式去遍歷。

對于樹，最好的方法就是遞歸遍歷（想好返回條件）。

其次：

1.最終要的是，遞歸要分析好return條件

2.當(dāng)需要深度遍歷時，一般需要借助下標(biāo) i

3.用到的是+ 而不是+=