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;
    }
};