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

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

• 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()];
}
}``````

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

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

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

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