WordBreak_I_BFS.cpp

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;
    }
};