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

• 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``````

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

• 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)
``````

• This post is deleted!

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