Word Break

又是一道动态规划的题目，当然个人感觉不那么明显，但是也有递推的逻辑存在。

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

1. The same word in the dictionary may be reused multiple times in the segmentation.
2. You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

一开始想简单了，直接上dfs来解，当然一个华丽的Time exceeded。一般这种题暴力dfs不成，最多的替代方法就是DP。以前有一题是找路线的条数，也是这个套路。

DP的基本思想基本是解出每一个路径的解，然后下一个解可以利用到前面的解，这里也大概相似，我们先求出0, … , n-1是否可以word break，然后再求出[0,n]是否可以word break，由于n之前是否可以已经知道了，所以我们只要从0开始，不断的求之前的子串是否可以word break，然后后面的子串是否可以word break，假设两者都可以，那么n就是可以word break的。当然我们只需要求后一个子串的就行，前面的子串由于是从0开始的，所以已经记录到结果集当中了。

比如例子

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

我们首先创建长度为8的记录flags，分别记录每个坐标点是否符合题目要求。然后分别求出8个的值。

我们先求s[0]，由于坐标从0开始，左子串不存在，不考虑，然后考虑右子串l是否在dict中，不符合，于是flags[0]=false。

然后求s[1]，从0开始不考虑，右子串为le，不存在，然后再移动坐标，左子串为l，我们这里可以不计算，因为已经记录在flags[0]中了，false其实就可以不用继续计算了,当然正常的逻辑下，假设为true，则需要计算后续的子串e是否在dict中。

下面为实现代码：

bool wordBreak(string s, vector<string>& wordDict) {
        // Dynamic programming
        if (wordDict.empty()) {
            return false;
        }
        unordered_set<string> wset(wordDict.begin(), wordDict.end());
        vector<bool> appear(s.size(), false);
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j <= i; j++) {
                bool preBreak = false;
                if (j == 0) {
                    preBreak = true;
                } else {
                    preBreak = appear[j - 1];
                }
                if (preBreak && wset.count(s.substr(j, i - j + 1)) != 0) {
                    appear[i] = true;
                    break;
                }
            }
        }
        return appear.back();
    }