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

说明：

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

示例 1：

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

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

1. 错误的解决方案
   考虑递归的方式，如果查找到匹配的单词，则判断剩余的字符串是否匹配。笔者最开始甚至实现了一个字典树。

struct CharTreeNode {
    char ch;
    bool end;
    vector<CharTreeNode> next;

    CharTreeNode() {
        ch = 0;
        end = false;
    }

    CharTreeNode(char c) {
        ch = c;
        end = false;
    }

    void SetEnd() {
        end = true;
    }

    CharTreeNode *AppendChar(char c) {
        for (int i = 0; i < next.size(); ++i) {
            if (next[i].ch == c) {
                return &next[i];
            }
        }
        next.push_back(CharTreeNode(c));
        return &next.back();
    }

    CharTreeNode *findChar(char c) {
        for (int i = 0; i < next.size(); ++i) {
            if (next[i].ch == c) {
                return &next[i];
            }
        }
        return nullptr;
    }
};

然后首先依据给定单词构造字典树，并递归查找是否匹配。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        BuildWordTree(wordDict);
        return wordSplitFind(s);
    }

    bool wordSplitFind(const string &s) {
        if (s.empty()) {
            return true;
        }
        CharTreeNode *p = &root;
        for (int i = 0; i < s.length(); ++i) {
            CharTreeNode *q = p->findChar(s[i]);
            if (q == nullptr) {
                return false;
            }
            if (q->end) {
                bool ret = wordSplitFind(s.substr(i + 1));
                if (ret) {
                    return true;
                }
                if (q->next.empty()) {
                    return false;
                }
            }
            p = q;
        }
        return false;
    }

    void BuildWordTree(vector<string> &words) {
        for (int i = 0; i < words.size(); ++i) {
            string &word = words[i];
            CharTreeNode *p = &root;
            for (int j = 0; j < word.length(); ++j) {
                p = p->AppendChar(word[j]);
            }
            p->SetEnd();
        }
    }

private:
    CharTreeNode root;
};

2. 动态规划算法
   上述算法对于特定情况下出现执行超时的问题。换一个思路，考虑动态规划算法。以字符串当前位置判断，设为i。则flag[i] = flag[j] && (s.substr(i, j - i) == word)。
   即：如果在之前j位置已经匹配，那么从j到i之间构成的字符串如果与某个单词匹配，则设置i位置也为true。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> flag(s.length() + 1, false);
        flag[0] = true;
        unordered_map<int, unordered_set<string>> mp;
        int min = 0, max = 0;
        for (int i = 0; i < wordDict.size(); ++i) {
            int len = wordDict[i].length();
            mp[len].insert(wordDict[i]);
            if (i == 0) {
                min = max = wordDict[i].length();
            } else {
                if (len > max) {
                    max = len;
                }
                if (len < min) {
                    min = len;
                }
            }
        }
        for (int i = 0; i < s.length(); ++i) {
            flag[i + 1] = false;
            int start = i + 1 - max;
            int end = i + 1 - min;
            for (int j = start < 0 ? 0 : start; j <= end; ++j) {
                if (!flag[j]) {
                    continue;
                }
                int diff = i + 1 - j;
                auto it = mp.find(diff);
                if (it == mp.end()) {
                    continue;
                }
                bool find = false;
                string tmp = s.substr(j, diff);
                for (auto iter = it->second.begin(); iter != it->second.end(); ++iter) {
                    if (tmp == *iter) {
                        find = true;
                        break;
                    }
                }
                if (find) {
                    flag[i + 1] = true;
                    break;
                }
            }
        }
        return flag.back();
    }
};