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

  • 1

    here is my recursive solution for this problem.

        `class Solution {
            bool wordBreak(string s, unordered_set<string> &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));
        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

    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

    Thank you, stellari!!

  • 0

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

  • 0

    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

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

  • 0

    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.