用7-4 的递归思路实现Letter Combination，为什么会更慢？

Question

老师，我根据7-4定义递归问题 BinaryTreePath 的递归思路实现Letter Combination，变慢了，不知道是我的实现问题还是算法本身确实比较慢？

我的思路： 比如digits="234", 在"34"返回的所有string前都加 “a”,“b”or “c”，再返回新的vector<string>。 如果是最后一个digits，则返回最后一个digit对应的几个字母。按照这个思路，可以减少了重复访问 “3”和“4”的次数，我觉得是更快的。

以下是我的code，在leetcode通过，3ms（课程实现代码0ms，怎么这么快，超越不了了＝_=）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

class Solution { private:     const string letterMap[10] = {             " ",    //0             "",     //1             "abc",  //2             "def",  //3             "ghi",  //4             "jkl",  //5             "mno",  //6             "pqrs", //7             "tuv",  //8             "wxyz"  //9     };       vector<string> findCombination(string digits,int index){         vector<string> res;           //for last index, return s[digits[digits.size()-1]]         if(index==digits.size()-1) {             char c = digits[index];             assert(c>='0'&&c<='9'&&c!='1');             string letters = letterMap[c-'0'];             for(int i=0;i<letters.size();i++) {                 string s1(1, letters[i]);                 res.push_back(s1);             }             return res;         }           // add s[digits[index]] to s[digits[0...index-1]]         char c = digits[index];         assert(c>='0'&&c<='9'&&c!='1');         string letters = letterMap[c-'0'];         vector<string> s = findCombination(digits, index+1);         for(int i=0;i<letters.size();i++){             for(int j=0;j<s.size();j++){                 string s1(1, letters[i]);                 string newS = s1 + s[j];                 cout<<"get "<<newS<<endl;                 res.push_back(newS);             }         }         return res;     }   public:     vector<string> letterCombinations(string digits) {         vector<string> res;         if(digits=="")             return res;           res = findCombination(digits,0);           return res;       } };

Answer 1

liuyubobobo 2017-08-05 01:18:38

首先，算法复杂度是一样的。你说的减少“3”和“4”的访问次数是不存在的。我的方法是从左向右生成字符串，你的方法实质上是从右向左生成字符串。你的方法是在"34"返回的所有string前都加 “a”,“b”or “c”；我的方法是在“23”得到的所有string后面加 “g”,“h”or “i”。如果你说减少了重复访问“34”结尾的情况，那我的方法就是减少了重复访问“23”开头的情况。事实上，这两种方式都是将每种情况做遍历，顺序不同而已，复杂性分析是一致的：）

但你的实现显然比我的实现处理了更多的内容，比如在findCombination中开辟了更多的string类型并且进行操作；同时维护s也是有成本的（每次返回res，都相当于又制造了一个res的副本！并且当digits长的时候，res会很大，在每一层递归都要记录维护这个很大的数组。）。仔细体会我的实现，res使用类中的成员变量，对于整个算法来说相当于是使用了全局变量：）

但其实你的思路其实完全可以根据我的代码结构做修改，把从左往右生成结果的方式修改成从右往左生成，感兴趣可以试试看：）

• 提问者 shanmufeng #1

  哈哈，谢谢老师详细的答疑^_^
  嗯嗯，确实是我实现的方法增加了重复访问“23”开头的情况，之前没想清楚。。。
  体会到使用类的成员变量（全局变量）的好处了，那是不是在递归、回溯问题中，如果涉及到保存大量数据，一般都会倾向于用这种成员变量的方法？

• 提问者 shanmufeng #2

  我想了下，回溯法用res 作为类的成员变量比较好实现，递归到底的时候就是问题的一个解，直接将结果保存到res成员变量就好了（就是老师你的实现了）。但是一般的递归，返回的一般都是中间量，需要再处理才能作为作为问题的一个解（比如我上面的实现，需要对“34”返回的结果再在前面加“2”）。这些中间量直接保存到res成员变量应该是不合适的，因为它们还要再区别地处理。这是回溯法的优点吧？

• liuyubobobo 回复 提问者 shanmufeng #3

  赞思考！你说的非常对！仔细想，其实在我的实现中，中间变量也已经通过参数传给下一层，并且这个传输过程的冗余度是很低的：）