Leetcode - 017. Letter Combinations of a Phone Number

原题地址

我的思路：
一个字符对应多种选择，需要遍历整个状态空间才能得到所求的ans，满足 dfs + backtracing组合求解模式。
1.每个char对应的可能性是确定的，map用来优化time cost
2.当前解的状态应该用 & ，虽然不使用 & 在本题也可以AC，出于backtracing 优化space cost的考虑，应该使用 &
3.dfs + backtring 的一般性套路即为：
3.1 在dfs中优先判断当前解是否为可行解
3.2 剪枝，pass明显不是解的状态空间
3.3 对于当前状态的所有可能的下行状态，用for循环，每次遵循(1.加入状态 2.dfs 3.撤回状态)即可完成dfs + backtraing的套路性求解

更多参考启发

class Solution {
public:
    map<int,string> mmp
    {{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},
     {'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    
    void dfs(vector<string> & vct,string &curans,string cur)
    {
        if(cur == "")
        {
            vct.push_back(curans);
            return;
        }
        string s = mmp[cur[0]];
        cur = cur.substr(1);
        for(int i = 0;i< s.length();++i)
        {
            curans += s[i];
            dfs(vct,curans,cur);
            curans = curans.substr(0,curans.length() - 1);
        }
    }
    
    vector<string> letterCombinations(string digits) {
        vector<string> vct;
        string s = "";
        if(digits.length() <= 0)
            return vct;
        dfs(vct,s,digits);
        return vct;
    }
};