Day130 | 靈神 | 回溯算法 | 子集型 電話號碼的字母組合
17.電話號碼的字母組合
17. 電話號碼的字母組合 - 力扣（LeetCode）
思路：
筆者用index代替i，這里的index其實就是digits數組的下標
按照靈神的回溯三問，那就是
1.當前的操作：找到本層要給path[index]里面填入哪個字母，很明顯的是每層就是一個數字的那幾個字母，所以就是選定一個數字然后從它的字母中選一個
2.子問題：構造字符串>=index的部分，其實也就是說明經過了index層選擇之后，我們已經確定了i位字母
3.下一個子問題：構造字符串>=index+1的部分，就是說明我們下一層的遞歸參數是index+1，因為我們已經在本層的字母中選擇了一個，所以要繼續往下走了，表現在數組上就是繼續往下遍歷digits
注意的細節：
映射的建立，下標要對上數字，也就是讓映射的數組從下標2開始而不是0，這樣會方便很多
完整代碼：
class Solution {
public:vector<string> res;vector<string> s{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void backtracking(string digits,string path,int index){if(index==digits.size()){res.push_back(path);return ;}int n=(int)(digits[index]-'0');for(int i=0;i<s[n].size();i++){path.push_back(s[n][i]);backtracking(digits,path,index+1);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0)return res;string path;backtracking(digits,path,0);return res;}
};靈神代碼：
靈神沒有"恢復現場"這一步，是因為靈神把path初始化為全0的字符串，并且在遞歸中直接覆蓋了對應的值，而恰巧字符串返回時的長度全都是digits數組的長度，所以把path放入結果集的時候肯定path數組都會被覆蓋一遍
class Solution {const string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public:vector<string> letterCombinations(string digits) {int n = digits.length();if (n == 0) {return {};}vector<string> ans;string path(n, 0); // 注意 path 長度一開始就是 n，不是空串auto dfs = [&](this auto&& dfs, int i) {if (i == n) {ans.emplace_back(path);return;}for (char c : MAPPING[digits[i] - '0']) {path[i] = c; // 直接覆蓋dfs(i + 1);}};dfs(0);return ans;}
};
