17. 電話號碼的字母組合 - 力扣（LeetCode）

思路：既然要排列組合，就得先根據數字字符取出來

所以先定義一個string類的數組通過下標取到每個數字對應的映射。

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

接下來便是：想到如果可以用遞歸，把每次組合的值返回（追加）到一個vector<string>對象中，且能回到上一個位置繼續，就能將全排列搞定。

因為通過di下標訪問數組，所以當di==digits.size()時，得到字符串，尾插到v中，返回上一級。

可以通過for循環訪問每一個數字映射的全部字符。

class Solution 
{
public:string _numsTostr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void Combine(const string& digits,int di,string cbstr,vector<string>& v){if(di==digits.size()){v.push_back(cbstr);return;}int num = digits[di]-'0';string str = _numsTostr[num];for(int i=0;i<str.size();i++){Combine(digits,di+1,cbstr+str[i],v);}}vector<string> letterCombinations(string digits) {vector<string> v;if(digits.empty()){return v;}Combine(digits,0,"",v);return v;}
};

注意：1.main函數加個if是因為防止用戶輸入為空，進到Combine里還會通過if尾插。

? ? ? ? ? ?2.其中的參數cbstr是保存每一次最后的字符串，把他尾插到v里，而遞歸往下走時的每一層字符由str加到cbstr里。

? ? ? ? ? ?3.這里傳的參數v，加了引用，目的是直接加到外面要返回的v里。

附上一部分自己畫的遞歸展開圖，方便理解。