# 139 - Word Break

解法一 - DP

這題只要先想到 subproblem DP[i] 就是 s[0]-s[i] 能否被 wordDict 裡面的 word 表示，要寫出 recurrence formula 就變得簡單不少。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> dp(n+1, false);
        dp[0] = true;

        set<string> table;
        for(auto w: wordDict)
            table.insert(w);

        for(int i=1; i<=n; i++) {
            for(int j=0; j<i; j++) {
                if(dp[j] == true) {
                    if(table.find(s.substr(j, i-j)) != table.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }

        return dp[n];
    }
};

/* idea: 
DP[i] stores if s[0]-s[i] can be expressed by word in wordDict
*/