What is the time complexity of the recursive solution for this problem? How to get it?


  • 1
    J

    here is my recursive solution for this problem.

        `class Solution {
        public:
            bool wordBreak(string s, unordered_set<string> &dict) {
                issegment=false;
                wordBreak(s,0,dict);
                return issegment;
            }
            void wordBreak(const string &s,int pos,unordered_set <string> &dict){
                if(pos==s.size()) issegment=true;
                if(issegment) return;
                for(int i=pos;i<s.size();i++){
                    auto iter=dict.find(s.substr(pos,i-pos+1));
                    if(iter!=dict.end()){
                        wordBreak(s,i+1,dict);
                    }
                }
            }
    
    private:
        bool issegment;
    };` 
    

    I want to know how to calculate the time complexity!
    I know that T(n)=n+T(n-1)+.T(n-2)+...+T(1);
    who can help me?


  • 9
    S

    Most recursive algorithm like this have an exponential time complexity. To see this, we expand T(n-1) to

    T(n-1) = k(n-1) + T(n-2) + T(n-3) + ... T(1) <=> T(n-1) - k(n-1) = T(n-2)+...+T(1) ---------- (1)
    

    and we already have

    T(n) = kn + T(n-1) + T(n-2) + ... + T(1) <=> T(n) - kn - T(n-1) = T(n-2) +... + T(1) ----------(2)
    

    Combine (1) and (2) we have:

    T(n) - kn - T(n-1) = T(n-1) - k(n-1) <=> T(n) = 2T(n-1) + k
    

    Therefore, we have O(n) = 2^n


  • 0
    J

    Thank you, stellari!!


  • 0
    M

    I suggest using an extra array to store information you get through calculation and save many steps.


  • 0
    H

    Here is my solution that actually passes the tests

    class Solution:
        def _wordBreak(self, s, dict):
            if not s:
                return True
            for v in dict:
                if v in s:
                    remains = s.split(v)
                    remains = filter(None, remains)
                    if not remains:
                        return True
                    result = reduce(
                        lambda x, y: self._wordBreak(y, dict) and x,
                        remains, True)
                    if result:
                        return True
            return False
    
        # @param s, a string
        # @param dict, a set of string
        # @return a boolean
        def wordBreak(self, s, dict):
            if not s:
                return True
            dict = sorted([w for w in dict if w in s], key=len, reverse=True)
            return self._wordBreak(s, dict)
    

    But I guess I cheated a bit there to actually filtered the dictionary before hand.
    If worst case happened then this will be screwed


  • 0
    H

    sorry a bit of cleanup there to polish out the useless bits


  • 0
    M

    Hi Stellari, your answer seems reasonable. But I can't understand how time complexity of this solution is different from problem like 'Combination Sum'? They both use recursion, and in each recursion layer, they iterate through a number of elements and recursively call the method with smaller problem size. But why the time complexity of Combination Sum is O(N!) while here this solution is O(2^n)?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.