# Time Limit Exceeded

• Last executed input:
s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";

dict = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"}

Here is my code:

``````class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
if (dict.empty()) return false; //dictionary is empty
unordered_set<string>::const_iterator match = dict.find(s);
if (match != dict.end()) return true; //the whole string is one dictionary word

for (unsigned int i = 1; i <= s.length(); i++){
string str = s.substr(0, i); //first substring of s from beginning to position i
match = dict.find(str);
if (match != dict.end()){
//if first substring is a dictionary word
//get the second substring which is the remaining part of string s
//if second substring is empty, return true
//else recursively call wordBreak on the second substring
string str2 = s.substr(i);
if (str2.empty()) return true;
else if (wordBreak(str2, dict)) return true;
//substring doesn't fit, continue iterating, increase i by 1
}
}
//after iterating through the whole string, not match found, return false
return false;
}
};``````

• You solve it by recursion. But it is not the best solution. Since the time complexity would be large.

You may think about using DP to solve it.

• O(n^2) solution:

``````class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
size_t length = s.size();
vector<vector<bool>> record(length, vector<bool>(length, false));

for(size_t i = 0; i < length; ++i){
for(size_t len = 0; len < length - i; ++len){
string subword = s.substr(i,len+1);
if(dict.find(subword) != dict.end()){
record[i][len] = true;
if(i > 0 && record[0][i-1]) record[0][i+len] = true;
}
}
}

return record[0][length-1];
}
};``````