WordBreak_I_DP.cpp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(wordDict.empty()) return false;
        int len_s = s.size();
        vector<int> dp(len_s + 1, 0);
        dp[len_s] = 1;
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        for(int i = len_s - 1; i>=0; i--){
            string tempS = "";
            for(int j = i; j < len_s; j++){
                tempS  += s[j];
                dp[i] = dict.count(tempS);
              // dp[i] here means whether substring[i, j] can be segmented
              //When the inner loop is over, dp[i] means whether substring[i, end] can be segmented
                if(dp[i]!=0 && dp[j+1] !=0)
                    break;
            }
        }
        return dp[0];
    }
};