题解 | #牛名生成器#

考察知识点：回溯、哈希

题目分析：

可以将数字到字母的映射存储到哈希表中，方便查找。

题意是说，要根据digits字符串中的数字，找到对应的字符串。然后在每一个字符串中取一个字符，组成与digits长度相等的名字。可以通过递归回溯的方法进行枚举。

其中，优选条件是字典序小的优先被选择。由于哈希表中字符串都是按字典序排列的，所以按照顺序遍历一遍即可。在一个字符串中选取好一个字符后，就开始选择下一个字符串中的最优字符。

注意回溯时应恢复现场。

所用编程语言：C++

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param digits string字符串 
     * @return string字符串vector
     */
    unordered_map<char, string> mp {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
    void backtrack(vector<string> &res, string &name, string &digits, int index) {
        if (index == digits.size()) {
            res.push_back(name);
            return;
        }
        for (auto &ch : mp[digits[index]]) {
            name += ch;
            backtrack(res, name, digits, index + 1);
            name.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        // write code here
        vector<string> res;
        string name = "";
        int size = digits.size();
        sort(digits.begin(), digits.end());
        backtrack(res, name, digits, 0);
        return res;
    }
};