Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(wordDict.empty()) return false;
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int len = wordDict.size();
vector<int> memo(s.size(), -1);
return dfs(0, s, memo, dict);
}
//Here memo[i] record the result of substring[0...i] and substring[i+1... len]
bool dfs(int start, string& s, vector<int>& memo, unordered_set<string>& dict){
if(start == s.size()) return 1;
if(memo[start] != -1) return memo[start];
string subS;
for(int i = start; i < s.size(); i++){
subS += s[i];
if(dict.count(subS) != 0 && dfs(i+1,s,memo,dict)){
return memo[start] = 1;
}
}
return memo[start] = 0;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment