Hi, anyone who knows the time-complexity of recursion with DFS? Here is the code


  • 0
    J
    bool wordBreakHelper(string s,int len, unordered_set<string> &dict, int pos)
        {
            if (pos == len)
                return true;
            for (int i = 1; i <= len - pos; i++)
            {
                string t = s.substr(pos, i);
                if (dict.find(t) != dict.end())
                {
                    if (wordBreakHelper(s, len, dict, pos + i))
                        return true;
                }
            }
            return false;
        }
        bool wordBreak(string s, unordered_set<string> &dict)
        {
            return wordBreakHelper(s, s.length(), dict, 0);
        }

  • 0
    V

    Time complexity is O(2^n) and that leads to TLE. Using Dynamic Programming approach it can be solved in
    O(string length * dict size).

    public class Solution {
        public boolean wordBreak(String s, Set<String> dict) {
            boolean[] t = new boolean[s.length()+1];
            t[0] = true; 
            for(int i=0; i<s.length(); i++){
                //should continue from match position
                if(!t[i]) 
                    continue;
     
                for(String a: dict){
                    int len = a.length();
                    int end = i + len;
                    if(end > s.length())
                        continue;
     
                    if(t[end]) continue;
     
                    if(s.substring(i, end).equals(a)){
                        t[end] = true;
                    }
                }
            }
     
            return t[s.length()];
        }
    }

  • 0
    J

    hi, I have no idea why the time complexity is O(2^n) ,could you explain it to me ?


  • 0
    Y

    hi, because there are 2^n different ways to divide the strings into subStrings. Think between every characters, there is two possible, divide it or not divide it. Two possible for n-1 slots, there are 2^(n-1) possible combination.


  • 0
    J

    The time complexity should be O(2^n).

    Let f(n) be the total loop times, where n is s.length() - pos, i.e. the length of the string.

    Given s="aaa…ab", dict=["a","aa","aaa",…"aaa…a"],

    • f(n) = f(n-1) + f(n-2) + … + f(1)
    • f(n-1) = f(n-2) + f(n-3) + … + f(1)
    • f(1) = 1

    then substitute f(n-1) in f(n):

    f(n) = ( f(n-2) + f(n-3) + … + f(1) ) + ( f(n-2) + f(n-3) + … + f(1) )
         = 2 × ( f(n-2) + f(n-3) + … + f(1) )
         = 2 × 2 × ( f(n-3) + f(n-4) + … + f(1) )
         = 2^(n-1)
    

    And searching in the dict take O(1) time in average. So the total time is O(2^n).


Log in to reply
 

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