class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        // dp[i]: sub string length i can be segament in Dict
        vector<bool> dp(n + 1, false);
        
        dp[0] = true;   
        
        // Because the order of the string is important
        // Iterate bag then iterate items
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                string sub = s.substr(j, i - j);
                if(dp[j] == true && wordSet.find(sub) != wordSet.end()) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }
};