题目一

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

思路

一个字符串能不能满足条件，我们很自然的想法就是：
如果"onetwothree"这一段可以拆分，再加上four如果也可以，那不就行了；
或者
如果"onetwothre"这一段可以拆分，再加上efour如果也可以，那不就行了；
这其实已经抓住了动态规划的最核心的东西了，换成式子来表达，就是

dp["onetwothreefour"] = dp["onetwothree"这一段] && 判断一下"four"
dp["onetwothreefour"] = dp["onetwothre"这一段] && 判断一下"efour"

Code

/*
    动态规划算法，dp[i]表示s前i个字符能否拆分
    转移方程：dp[j] = dp[i] && check(s[i+1, j]);
    check(s[i+1, j])就是判断i+1到j这一段字符是否能够拆分
    其实，调整遍历顺序，这等价于s[i+1, j]是否是wordDict中的元素
    这个举个例子就很容易理解。
    假如wordDict=["apple", "pen", "code"],s = "applepencode";
    dp[8] = dp[5] + check("pen")
    翻译一下：前八位能否拆分取决于前五位能否拆分，加上五到八位是否属于字典
    （注意：i的顺序是从j-1 -> 0哦~
*/
class Solution {
public:
    unordered_map<string, bool> map;

    bool check(string str) {
        return map[str];
    }

    bool wordBreak(string s, vector<string> &wordDict) {
        int size = s.size();
        bool dp[size + 1];
        memset(dp, false, sizeof(dp));
        //构建一个哈希表，方便查询
        for (auto str:wordDict) {
            map[str] = true;
        }

        dp[0]=true;
        for (int j = 0; j <= size; j++) {
            for (int i = j - 1; i >= 0; i--) {
                dp[j] = dp[i] && check(s.substr(i, j - i ));
                if (dp[j]) break;
            }
        }
        return dp[size];
    }
};