139. Word Break

做题历程：

1. 本题做了不止2遍了，本次独立解出，大概耗时14分钟

本题开始我有点纠结，我一看题，以为应该有O(N)的解法，然而事实上高票解法都是O(N^2)，所以也就放心了，大体思路就是Dynamic Programming:

1. 两层for loop，外层测开始的index
2. 内层测从外层index开始的substring
3. 不断更新vector<bool> dp的元素，最后检查最后一个元素dp.last()

代码比单纯的叙述要清晰，代码如下：

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