Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

思路：DP。

维护一个一维bool类型数组DP[]。DP[i]表示字符串S从第0位到第i位子串是否能够分割成字典里的单词。

然后遍历一遍字典，记录下字典中单词的最大长度和最小长度，分别记为max_l和min_l。

之后进行二重循环，外层循环枚举的是单词在S中的结束位置，因为已知最短的单词长为min_l，设S长为n，则枚举的范围是min_l - 1到n - 1。

内层循环枚举的是单词的开始位置，即以外层循环所枚举的结束位置为基准，向前找min_l到max_l的距离，更近或更远都不可能存在单词了。

这里注意一个点，内层循环在枚举了一个开始位置后，设其为i，若i不为0，则判断下dp[i - 1]是否为true，若为false则直接continue。因为若前面都无法由单词构成，则这里就算由单词构成也没什么用。

最后dp[n - 1]即为结果。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        if (n == 0) return false;
        vector<bool> dp(n, false);
        unordered_set<string>::iterator iter = wordDict.begin();
        unordered_set<string>::iterator end = wordDict.end();
        int max_l = INT_MIN;
        int min_l = INT_MAX;
        for (; iter != end; iter++)
        {
            int size = iter->size();
            max_l = max(max_l, size);
            min_l = min(min_l, size);
        }
        for (int i = min_l - 1; i < n; i++)
            for (int j = i - min_l + 1; j >= 0 && j >= i - max_l + 1; j--)
            {
                if (j - 1 >= 0 && !dp[j - 1]) continue;
                string word = s.substr(j, i - j + 1);
                if (wordDict.count(word) > 0) dp[i] = true;
            }
        return dp[n - 1];
    }
};