题解 | #训练聪明的牛#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是字符串处理和动态规划（DP）算法。

题目解答方法的文字分析

我们需要判断这头牛是否可以把长字符串 s 拆分成词汇表 wordDict 中的单词。我们可以使用动态规划来解决这个问题。

首先，我们定义一个一维的 DP 数组 dp，其中 dp[i] 表示 s 的前 i 个字符是否可以拆分成词汇表中的单词。

接下来，我们来考虑动态规划的转移方程。对于 dp[i]，我们可以枚举所有词汇表中的单词，如果存在一个单词 word，满足 s 的前 i 个字符的结尾是该单词 word，则 dp[i] = true，表示 s 的前 i 个字符可以拆分成词汇表中的单词。

最后，我们需要初始化 DP 数组的边界条件。dp[0] 表示空字符串是否可以拆分成词汇表中的单词，显然是 true。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param wordDict string字符串vector 
     * @return bool布尔型
     */
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());

        // 定义一维 DP 数组
        vector<bool> dp(n + 1, false);

        // 初始化边界条件
        dp[0] = true; // 空字符串可以拆分

        // 动态规划递推
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                // 枚举所有词汇表中的单词
                string word = s.substr(j, i - j);
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    // 如果存在一个单词满足 s 的前 i 个字符的结尾是该单词，则可以拆分
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！