# Help! time limit exceeded.

• My solution exceeds the time limit. Can anybody explain it? Thanks!

``````class Solution {
public:

vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
unordered_map<int,vector<string>> res;
vector<bool> bl(s.length(),false);
for(int i=0;i<s.length();i++){
for(int j=0;j<i;j++){
if(bl[j] && wordDict.find(s.substr(j+1,i-j))!=wordDict.end()){
bl[i]=true;
for(string& ins : res[j]){
string tmpstr=ins+" "+s.substr(j+1,i-j);
res[i].push_back(tmpstr);
}
}
}
if(wordDict.find(s.substr(0,i+1))!=wordDict.end()){
bl[i]=true;
res[i].push_back(s.substr(0,i+1));
}
}
return res[s.length()-1];
}
};``````

• well, I just met the same problem and solved it successfully. May I can help you :)
First, in your loop of j, you use

``````for(int j=0;j<i;j++)
``````

Let n=s.length(), this loop will run n times. If s is very long, it may take a lot of time.
Let m=maximum length of words in wordDict, then you just need to range j from i-m to i. The loop will be

``````for(int j=max(0, j-m); j<i; j++)
``````

Second, your DP method will lead to an explosion in some special cases. For instance, suppose s is "aaaaa", and wordDict contains all strings which are formed with different numbers of "a", that is wordDict={"a", "aa", "aaa", "aaaa", ......}.
According to your method, res[0]={"a"}, res[1]={"aa", "a a"}, res[2]={"aaa", "a aa", "aa a", "a a a"}. As you can see, the number of res[i] will increase exponentially. If s is very long, the time and space costs will be too large. If s="aaaaaaabaaaaaa", it can't be broken with given wordDict because there is one 'b' in it. However, in your DP method, you have to use exponential time to calculate res[i], at least before 'b'.
When there are more 'a' before and after the 'b', you will get a TLE.
So, my solution is to check whether the s can be broken by wordDict.