139_Word_Break

BFS MLE
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        queue<string> q;
        q.push(s);
        while (!q.empty()){
            string current = q.front();
            q.pop();
            for (int i = 0; i < wordDict.size(); ++i){
                if (current == wordDict[i]) return true;
                if (current.substr(0, wordDict[i].size()) == wordDict[i]){
                    q.push(current.substr(wordDict[i].size()));
                }
            }
        }
        return false;
    }
};

BFS use hashset as queue
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> q;
        q.insert(s);
        while (!q.empty()){
            unordered_set<string> thistime = q;
            for (auto it = thistime.begin(); it != thistime.end(); ++it){
                string current = *it;
                q.erase(*it);
                for (int i = 0; i < wordDict.size(); ++i){
                    if (current == wordDict[i]) return true;
                    if (current.substr(0, wordDict[i].size()) == wordDict[i] && q.count(current.substr(wordDict[i].size())) == 0){
                    q.insert(current.substr(wordDict[i].size()));
                }
                }
                
            }
        }
        return false;
    }
};

DP

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp (s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i < dp.size(); ++i){
            for (int j = 1; j <= i; ++j){
                string t = s.substr(i - j, j);
                if (find(wordDict.begin(), wordDict.end(), t) != wordDict.end()){
                    dp[i] = dp[i - j];
                    if (dp[i] == true) break;
                }
            }
        }
        return dp[dp.size() - 1];
    }
};

DP

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp (s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i < dp.size(); ++i){
            for (int j = 1; j <= i; ++j){
                if (dp[i - j]){
                    string t = s.substr(i - j, j);
                    if (find(wordDict.begin(), wordDict.end(), t) != wordDict.end()){
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[dp.size() - 1];
    }
};