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

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

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

输入：数字串 “23”

输出： “AD”， “AE”， “AF”， “BD”， “是”， “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; 
    } 
};

来源

2014-11-21 Happy Coder

在你的循环在这里：

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

比方说tmp是，当你走过你的循环会发生什么？首先你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); 
}

这就是为什么“正确的”溶胶你发布的作品，你不会失败。

来源

2014-11-21 20:34:14 Barry

非常感谢！即使在我花了很多时间之后，我仍然还没有完全理解回溯和递归。我确实发现了当我逐步调试时发生的情况，但无法弄清楚为什么正确答案有效。 – 2014-11-21 21:20:12

你碰巧有一个很好的资源/书阅读，以更好地学习它？再次感谢！ – 2014-11-21 21:20:41

@HappyCoder没有什么比调试体验更胜一筹。正确的答案是有效的，因为在循环中，你用''a''，然后''b''，然后''c“递归，而在你最初的尝试中，你用''a”'递归，那么'“ab”'，然后'“abc”'。你明白他们为什么做不同的事情吗？你明白为什么只有前者是正确的吗？有时候，从超简单的案例开始就会有帮助：'letterCombinations（“2”）'最好能给你回3件事吗？ – Barry 2014-11-21 21:43:27

我看到

combo.push_back问题（TMP [J]）;

它`正确对于j == 0，但错对于j！= 0

例如如果j == 1.您`ll放至BT功能组合+ TMP [0] + tmp [1]而不是combo + tmp [1]。

来源

2014-11-21 20:41:37

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

回答

相关问题