题解 | #牛名生成器#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察如何使用回溯法来生成所有可能的牛名组合。

题目解答方法的文字分析

我们可以使用回溯法来生成所有可能的牛名组合。回溯法是一种递归的搜索算法，通过不断地做选择和撤销选择来得到所有可能的结果。

具体步骤如下：

1. 使用一个数组letters来保存数字到字母的映射。
2. 定义一个递归函数，该函数有四个参数：当前正在生成的牛名组合prefix、当前数字在digits中的索引idx、digits字符串和结果集res。
3. 如果idx等于digits的长度，表示已经处理完了所有数字，将当前的牛名组合加入结果集res中。
4. 否则，获取当前数字对应的所有字母，并遍历这些字母。
5. 对于每个字母，将其加入牛名组合prefix中，并递归调用函数处理下一个数字（idx+1）。
6. 在递归调用后，需要撤销对牛名组合的选择，以便继续处理其他字母。
7. 返回结果集res作为最终答案。

本题解析所用的编程语言 (C++)

C++

完整且正确的编程代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res; // 结果集
        if (digits.empty()) {
            return res;
        }

        vector<string> letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        string prefix; // 当前正在生成的牛名组合
        backtrack(prefix, 0, digits, letters, res);

        return res;
    }

private:
    void backtrack(string prefix, int idx, const string& digits, const vector<string>& letters, vector<string>& res) {
        if (idx == digits.length()) {
            res.push_back(prefix); // 当前牛名组合生成完毕，加入结果集
            return;
        }

        int num = digits[idx] - '0'; // 当前数字
        string letter = letters[num]; // 当前数字对应的字母

        for (char c : letter) {
            prefix.push_back(c); // 加入当前字母到牛名组合
            backtrack(prefix, idx + 1, digits, letters, res); // 处理下一个数字
            prefix.pop_back(); // 撤销选择，以便继续处理其他字母
        }
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！