C++_DP_Accepted_9ms (Recursive Method: TLE)

• ``````class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
if(wordDict.empty()) return false;
vector<bool> DP(s.size() + 1,false);
DP[0] = true;
for(int i = 1; i < DP.size(); i++){
for(int j = i - 1; j >= 0; j--){
if(DP[j]){
string t = s.substr(j, i - j);
if(wordDict.find(t) != wordDict.end()){DP[i] = true;break;}
}
}
}
return DP[s.size()];
}
};
``````
• TLE: Following is my original methods, I just want to use every s[i] as a cutting point to find out whether they could be found in the wordDict.
• The DP methods is also very similar. Using the vector to store previous information, which DP[i] means that is DP[i] = true, then the string from s[0] to s[i-1] is available in the wordDict.
• (That's also the reason why the length of DP is s.size() + 1 rather than s.size() )
``````#code block

//Time Limit Exceed
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
if(wordDict.empty()) return false;
int n = s.size();
if (wordDict.find(s) != wordDict.end()){return true;}
bool res = true;
for(int i = 1; i < n; i++){
string s1 = s.substr(0,i);
string s2 = s.substr(i);
bool res1 = wordDict.find(s1) != wordDict.end();
bool res2 = wordDict.find(s2) != wordDict.end();
if(res1 && res2){ return true;}
else if(!res1 && res2 && wordBreak(s1, wordDict)){return true;}
else if(res1 && !res2 && wordBreak(s2, wordDict)){return true;}
else if(wordBreak(s1, wordDict) && wordBreak(s2, wordDict)) {return true;}
}
return false;
}
};
``````

[alt text]( image url)A69E2C7C-1416-4248-8C2D-EC11C20050BE.png

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