题解 | #牛名生成器#

知识点：

哈希表/回溯/DFS

分析：

首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完生成器的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取生成器的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理生成器的后一位数字，直到处理完生成器中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。回溯法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

编程语言:

C++

完整代码：

 vector<string> res;
    string path;
    const string letterMAP[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    void dfs(string digits,int u){
        if(u == digits.size()) res.push_back(path);
        for(int i = 0;i < letterMAP[digits[u] - '0'].size();i++){
            path.push_back(letterMAP[digits[u] - '0'][i]);
            dfs(digits,u+1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return res;
        dfs(digits,0);
        return res;
    }