# What is the time complexity of the recursive solution for this problem? How to get it?

• here is my recursive solution for this problem.

``````    `class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
issegment=false;
wordBreak(s,0,dict);
return issegment;
}
void wordBreak(const string &s,int pos,unordered_set <string> &dict){
if(pos==s.size()) issegment=true;
if(issegment) return;
for(int i=pos;i<s.size();i++){
auto iter=dict.find(s.substr(pos,i-pos+1));
if(iter!=dict.end()){
wordBreak(s,i+1,dict);
}
}
}

private:
bool issegment;
};`
``````

I want to know how to calculate the time complexity!
I know that T(n)=n+T(n-1)+.T(n-2)+...+T(1);
who can help me?

• Most recursive algorithm like this have an exponential time complexity. To see this, we expand T(n-1) to

``````T(n-1) = k(n-1) + T(n-2) + T(n-3) + ... T(1) <=> T(n-1) - k(n-1) = T(n-2)+...+T(1) ---------- (1)
``````

``````T(n) = kn + T(n-1) + T(n-2) + ... + T(1) <=> T(n) - kn - T(n-1) = T(n-2) +... + T(1) ----------(2)
``````

Combine (1) and (2) we have:

``````T(n) - kn - T(n-1) = T(n-1) - k(n-1) <=> T(n) = 2T(n-1) + k
``````

Therefore, we have O(n) = 2^n

• Thank you, stellari!!

• I suggest using an extra array to store information you get through calculation and save many steps.

• Here is my solution that actually passes the tests

``````class Solution:
def _wordBreak(self, s, dict):
if not s:
return True
for v in dict:
if v in s:
remains = s.split(v)
remains = filter(None, remains)
if not remains:
return True
result = reduce(
lambda x, y: self._wordBreak(y, dict) and x,
remains, True)
if result:
return True
return False

# @param s, a string
# @param dict, a set of string
# @return a boolean
def wordBreak(self, s, dict):
if not s:
return True
dict = sorted([w for w in dict if w in s], key=len, reverse=True)
return self._wordBreak(s, dict)
``````

But I guess I cheated a bit there to actually filtered the dictionary before hand.
If worst case happened then this will be screwed

• sorry a bit of cleanup there to polish out the useless bits

• Hi Stellari, your answer seems reasonable. But I can't understand how time complexity of this solution is different from problem like 'Combination Sum'? They both use recursion, and in each recursion layer, they iterate through a number of elements and recursively call the method with smaller problem size. But why the time complexity of Combination Sum is O(N!) while here this solution is O(2^n)?

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