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);
}
Hi, anyone who knows the timecomplexity of recursion with DFS? Here is the code


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

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(n1) + f(n2) + … + f(1)
 f(n1) = f(n2) + f(n3) + … + f(1)
 …
 f(1) = 1
then substitute f(n1) in f(n):
f(n) = ( f(n2) + f(n3) + … + f(1) ) + ( f(n2) + f(n3) + … + f(1) ) = 2 × ( f(n2) + f(n3) + … + f(1) ) = 2 × 2 × ( f(n3) + f(n4) + … + f(1) ) = 2^(n1)
And searching in the dict take O(1) time in average. So the total time is O(2^n).