题解 | #训练聪明的牛#

考察的知识点：动态规划；

解答方法分析：

1. 创建一个动态规划数组dp，dp[i]表示从0到i的子串能否被拆分成词汇表中的单词。
2. 使用一个双重循环来遍历字符串s的所有子串。外层循环遍历每个子串的末尾位置，内层循环遍历每个子串的起始位置。
3. 在内层循环中，判断当前子串是否在词汇表中。如果当前子串在词汇表中，更新dp数组，将dp[i]置为true。
4. 返回dp数组的最后一个元素，即dp[s.size()-1]，表示整个字符串s能否被拆分成词汇表中的单词。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param wordDict string字符串vector
     * @return bool布尔型
     */
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};