leetcode 电话号码组合题执行错误，如何解决？

Question

leetcode 电话号码组合题执行错误

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

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码中，主要实现了一个基于递归的电话号码组合生成算法。从错误描述来看，没有具体的执行错误内容，所以我将对整个解决方案进行审查，并提供可能的问题点及修改后的完整代码。

问题1：原始代码中的merge_combination函数在递归结束后没有正确地回溯（即恢复combination的状态）。在每次递归调用前应保存当前的combination状态，并在递归返回后恢复。

修正后的 Solution 类：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, string> phmap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        vector<string> letterCombinations;
        merge_combination(phmap, letterCombinations, digits, "", 0);
        return letterCombinations;
    }

    void merge_combination(unordered_map<char, string>& phmap, vector<string>& letterCombinations, const string& digits, string combination, int i) {
        if (i == digits.size()) {
            letterCombinations.push_back(combination);
            return;
        }
        
        string index = phmap[digits[i]];
        for (int k = 0; k < index.size(); ++k) {
            // 保存当前 combination 状态
            string nextCombination = combination + index[k];
            // 进行下一层递归并恢复 combination
            merge_combination(phmap, letterCombinations, digits, nextCombination, i + 1);
        }
    }
};

在这个修正后的版本中，我做了以下更改：

1. 初始化 letterCombinations 时传入空字符串 "" 而不是直接在类成员变量里初始化。
2. 修改了判断递归结束条件，当 i 等于 digits.size() 时说明已经遍历完所有数字，此时添加 combination 到结果集中。
3. 在循环内部创建一个新的 nextCombination 字符串用于存储新的组合，在下一次递归调用之后，这个临时变量不会影响到之前的 combination。

这样就能确保正确生成所有的电话号码字母组合了。