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());
unordered_set<int> visited;
queue<int> q({0}); //Queue initialization should include container
while(!q.empty()){
int next = q.front();
q.pop();
if(visited.count(next)!=0) continue;
visited.insert(next);
string tempS = "";
for(int i = next; i < s.size(); i++){
if(dict.count(tempS += s[i]) != 0){
q.push(i+1);
if(i+1 == s.size()) return true;
}
}
}
return false;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment