17. 电话号码的字母组合

每一个数字对应了几个字母，把数字串转化为字母串，其实就是要去枚举

可以直接使用循环按照一个数字一个数字，去枚举字母，还可以利用dfs来枚举
这里我使用map来存储，其实也可以使用其他数据结构来存储，例如
map>, map, map>, vector 使用vector的时候能够使用下标来标识

第一种：循环

class Solution {
   vector<string> res;
   string _digits;
   unordered_map<int,string> mp;
public:
   vector<string> letterCombinations(string digits) {
       if(digits == "") return vector<string>();
       _digits = digits;
       int idx = 0;
       mp.insert({0,"abc"});
       mp.insert({1,"def"});
       mp.insert({2,"ghi"});
       mp.insert({3,"jkl"});
       mp.insert({4,"mno"});
       mp.insert({5,"pqrs"});
       mp.insert({6,"tuv"});
       mp.insert({7,"wxyz"});
       vector<string> v1, v2;
       v1.push_back("");
       for(int i = 0; i < digits.size(); i++)
       {
           for(auto x: v1)
           {
               for(auto y: mp[digits[i] - '0' - 2])
               {
                   string s = x+y;
                   v2.push_back(s);
               }
           }
           v1 = v2;
           v2.clear();
       }
       return v1;
   }
};

第二种： dfs

class Solution {
   vector<string> res;
   string _digits;
   unordered_map<int,string> mp;
   void dfs(int idx, string s)
   {
       if(idx == _digits.size())
       {
           res.push_back(s);
           return;
       }
       for(auto x: mp[_digits[idx] - '0' - 2])
       {
           string ns = s + x;
           dfs(idx+1, ns);
       }
       return;
   }
public:
   vector<string> letterCombinations(string digits) {
       if(digits == "") return vector<string>();
       _digits = digits;
       int idx = 0;
       mp.insert({0,"abc"});
       mp.insert({1,"def"});
       mp.insert({2,"ghi"});
       mp.insert({3,"jkl"});
       mp.insert({4,"mno"});
       mp.insert({5,"pqrs"});
       mp.insert({6,"tuv"});
       mp.insert({7,"wxyz"});
       string s = "";
       dfs(idx, s);
       return res;
   }
};

class Solution {
    vector<string> res;
    vector<string> mp;
    void dfs(string digits, int idx, string path)
    {
        if(idx == digits.size())
        {
            res.push_back(path);
            return;
        }
        for(auto x: mp[digits[idx] - '0'])
        {
            dfs(digits, idx + 1, path + x);
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(!digits.size()) return res;
        mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        dfs(digits, 0,"");
        return res;
    }
};

第三种动态规划

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(!digits.size()) return vector<string>();
        vector<string> mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int n = digits.size();
        vector<vector<string>> f(n + 1);
        f[0].push_back("");
        for(int i = 1; i <= n; i++)
        {
            int val = digits[i - 1] - '0';
            for(auto x: f[i - 1])
            {
                for(auto y: mp[val])
                {
                    f[i].push_back(x + y);
                }
            }
        }
        return f[n];
    }
};

第二次写题

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(!digits.size()) return vector<string>();
        vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> res = {""};
        for(auto d: digits)
        {
            int n = d - '0';
            vector<string> tmp;
            for(auto c: v[n])
            {
                for(auto s: res)
                {
                    tmp.push_back(s + c);
                }
            }
            res = tmp;
        }
        return res;
    }
};