Can anyone tell me what's the time complexity of my code. DFS


  • 0
    X

    The idea is simple, as long as the left part and the right part of a string are both contained in the dict, then the whole string is breakable.
    Here is the code. It got a TLE, can anyone tell me what's the time complexity of my code. THX!

    def wordBreak1(self, s, dict):
    	# brute force DFS
    	if not dict:
    		return False
    	if not s:
    		return True
    
    	if s in dict:
    		return True
    	for isep in range(1, len(s)):
    		l = self.wordBreak1(s[:isep], dict)
    		r = self.wordBreak1(s[isep:], dict)
    		if l and r:
    			return True
    	return False

  • 0
    M

    You are doing recursion. Use DP instead. With recursion, you are calculating same things again and again!


  • 1
    S

    Although this solution uses practically brute force, I can still show you how to analyze its time complexity so that you'll have an idea how bad it is.

    Suppose the running time of this function given an input string of length n is f(n). Consider the for loop of n iterations in your code. The running time each iteration takes is:

    1: f(1) + f(n-1)
    2: f(2) + f(n-2)
    ...
    n: f(n-1) + f(1)
    

    That's pretty much all the running time this function needs. So we have:

    f(n) = 2[f(1) + f(2) + ... + f(n-1)]
    

    To see what that is in big-O notation, simply calculate f(n-1) first:

    f(n-1) = 2[f(1) + f(2) + ... + f(n-2)]
    

    then substitute f(n-1) into f(n), we have:

    f(n) = 2{f(1) + f(2) + ... + 2[f(1) + f(2) + ... + f(n-2)]}
         = 6[f(1) + f(2) + ... + f(n-2)]
    	 = 3f(n-1)
    

    so each time you add 1 more character to the input string, the running time triples. Naturlaly, the time complexity of your algorithm would be

    O(3^n)
    

  • 0
    J
    This post is deleted!

Log in to reply
 

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