题解 | #训练聪明的牛#

一、知识点：

动态规划

二、文字分析：

我们定义一个长度为n的布尔数组dp，其中dp[i]表示字符串s的前i个字符是否可以由词汇表中的单词拆分而成。

状态转移方程为：

• 如果dp[j]为true且字符串s从第j+1个字符到第i个字符（即s.substring(j+1, i+1)）在词汇表中，也即wordDict.contains(s.substring(j+1, i+1))为true，则dp[i]为true。

初始化：

• dp[0]为true，表示空字符串可以由词汇表中的单词拆分而成。

最终结果为dp[n]，其中n为字符串s的长度。

时间复杂度：

• 两层循环遍历字符串s的所有子串，时间复杂度为O(n^2)。
• 在内层循环中，判断子串是否在词汇表中需要O(1)的时间（使用Set存储词汇表并进行查找）。

因此，算法的总体时间复杂度为O(n^2)。

空间复杂度：

• 需要一个长度为n+1的布尔数组dp来保存每个子串是否可以拆分成词汇表中的单词，空间复杂度为O(n+1)。
• 需要一个Set来存储词汇表中的单词，空间复杂度取决于词汇表的大小，可以认为是O(m)，其中m是词汇表中单词的数量。

因此，算法的总体空间复杂度为O(n+m)。

三、编程语言：

java

四、正确代码：

import java.util.*;


public class Solution {
    public boolean wordBreak(String s, String[] wordDict) {
        int n = s.length();
        Set<String> wordSet = new HashSet<>(Arrays.asList(wordDict));

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}