传递参数递归 C++(电话号码的字母组合)

Question

问题如下。

给定一个数字字符串，返回该数字可以表示的所有可能的字母组合。

下面给出了数字到字母的映射（就像在电话按钮上一样）。

输入：数字字符串"23"

输出： ["ad"， "ae"， "af"， "bd"， "be"， "bf"， "cd"， "

ce"， "cf"]。

我使用了回溯，但无法弄清楚为什么答案是错误的......猜猜我不熟悉递归调用如何在传递的参数上工作。

有人可以帮助我吗？多谢！错：

class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    vector<string> letterCombinations(string digits) {
        int len =digits.size();
        vector<string> res;
        string combo;
        bt( res, combo,digits, len, 0);
        return res;
    }
    void bt(vector<string> &res, string combo, string digits, int len, int i)
    {
         if (i==len)
         {
             res.push_back(combo);
             return;
         }
         int idx = digits[i]-'0';
         if (idx<0||idx>9)
             return;
         string tmp = keyboard[idx];
         int s=tmp.size();
         for (int j=0; j<s; j++)
            {
                combo.push_back(tmp[j]);
                i++;
                bt(res,combo,digits,len,i); 
            }
    }
};

正确：

class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    vector<string> letterCombinations(string digits) {
        int len =digits.size();
        vector<string> res;
        string combo;
        bt( res, combo,digits, len, 0);
        return res;
    }
        void bt(vector<string> &res, string combo, string digits, int len, int i)
        {
            if (combo.size() == len)
            {
                res.push_back(combo);
                return;
            }
            int idx = digits[i] - '0';
            string tmp = keyboard[idx];
            int s = tmp.size();
            for (int j = 0; j<s; j++)
            {
                bt(res, combo + tmp[j], digits, len, i+1);
            }
        }
};

后来我发现使用 BFS 对我来说更直观，并使我的代码更简洁。或者有什么更好的方法来编写没有递归的？再次感谢！

class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    vector<string> letterCombinations(string digits) {
        vector<string> res(1, "");
        string combo;
        int n=digits.size();
        vector<string> tmp;
        for(int i=0; i<n; i++)
        {
            int m = keyboard[digits[i]-'0'].size();
            int rsize =res.size();
            for (int k=0; k<rsize; k++)
            {
                string ts = res[k];
                for (int j=0; j<m; j++)
                   {
                    res[k] = res[k] + keyboard[digits[i]-'0'][j];
                    tmp.push_back(res[k]);
                    res[k] = ts;
                   }
            }
            res = tmp;
            tmp.clear();
        }
        return res;
    }
};

Answer 1

在你的循环中：

for (int j=0; j<s; j++)
{
    combo.push_back(tmp[j]);
    i++;
    bt(res,combo,digits,len,i); 
}

假设tmp "abc"，当你走过循环时会发生什么？首先，您push_back('a')并增加i...然后你push_back('b')并再次递增i！您需要回溯：

艰难的方式：

for (int j=0; j<s; j++)
{
    combo.push_back(tmp[j]);
    i++;
    bt(res,combo,digits,len,i); 
    combo.erase(i);
    --i;
}

更简单的方法：

for (int j=0; j<s; j++)
{
    bt(res,combo + tmp[j],digits,len,i + 1); 
}

最简单的方法：认识到combo.size() == i是不变的，并删除一个变量：

for (int j=0; j<s; j++)
{
    bt(res,combo + tmp[j],digits,len); 
}

这就是为什么您发布的"正确"解决方案有效，您不会回溯。

Answer 2

我看到了问题

combo.push_back（TMP[j]）;

对于 j == 0 是正确的，但对于 j ！= 0 是错误的。

例如，如果 j == 1。你将使用 bt 函数 combo + tmp[0] + tmp[1] 而不是 combo + tmp[1]。