题解 | #训练聪明的牛#

知识点：

字符串/动态规划

分析：

使用动态规划来解，还是先来定义状态，问题是确定字符串s是否可以被分割

状态表示：

字符串的前i个字符是否可以被分割。

这样就可以去判断前1个字符是否可以被分割

状态转移方程：f(i) = f(j) && s[j] ~ s[i - 1]是否可以被分割；

初始状态：f(0) = true；

返回结果：f(s.size())；

编程语言：

C++

完整代码：

    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for(auto wd : wordDict) dict.insert(wd);
        vector<bool> v(s.size() + 1, false);
        v[0] = true;
        for (int i = 1; i < v.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (v[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    v[i] = true;
                    break;
                }
            }
        }
        return v[s.size()];
    }