题解 | #牛名生成器#

考察的知识点：回溯；

解答方法分析：

1. 将数字和字母的映射关系以键值对的形式存储在一个哈希表中。这样可以方便地根据给定的数字获取对应的字母字符串。
2. 定义一个辅助函数 backtrack，在其中进行回溯操作。回溯函数的参数包括当前的组合字符串，当前数字字符串的索引以及数字字符串本身。
3. 在回溯函数中，首先判断当前数字字符串的索引是否等于数字字符串的长度，如果相等，则将当前组合字符串添加到结果列表中。
4. 根据当前数字获取对应的字母字符串。遍历字母字符串，将每个字母加入到当前组合字符串，并递归调用回溯函数，传递更新后的参数。这样可以探索到所有可能的组合。
5. 递归结束后，我们需要将当前加入的字母从组合字符串中移除，以便进行下一次迭代。
6. 返回结果列表。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.empty()) {
            return res;
        }
        unordered_map<char, string> letters = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        backtrack(res, letters, combination, digits, 0);
        return res;
    }
  private:
    void backtrack(vector<string>& res, unordered_map<char, string>& letters,
                   string& combination, string& digits, int index) {
        if (index == digits.size()) {
            res.push_back(combination);
            return;
        }
        string lettersStr = letters[digits[index]];
        for (char c : lettersStr) {
            combination.push_back(c);
            backtrack(res, letters, combination, digits, index + 1);
            combination.pop_back();
        }
    }
};