用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，怎么这么快，超越不了了＝_=）

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

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