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();
return dfs(0, s, dict);
}
bool dfs(int start, string& s, unordered_set<string>& dict){
if(start == s.size()) return 1;
string subS;
for(int i = start; i < s.size(); i++){
subS += s[i];
if(dict.count(subS) != 0 && dfs(i+1,s,dict)){
return 1;
}
}
return 0;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment