139 单词拆分

一、题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

二、题解

思路：动态规划。

1. 核心思路

这道题要判断字符串 s 能不能由字典 wordDict 中的单词拼接出来。

我们可以使用动态规划来解决。

定义：

dp[i] 表示字符串 s 的前 i 个字符能否被字典中的单词拼接出来

也就是：

dp[i] 表示 s[0...i-1] 能否被拆分

例如：

s = "leetcode"
dp[4] 表示 "leet" 能否被拆分
dp[8] 表示 "leetcode" 能否被拆分

如果存在一个切分点 j，满足：

dp[j] == true

并且：

s.substring(j, i)

在字典中，那么说明：

s[0...j-1] 可以被拆分
s[j...i-1] 是字典中的一个单词

所以：

s[0...i-1] 也可以被拆分

因此可以令：

dp[i] = true

2. 具体步骤

  1. 将 wordDict 放入 HashSet 中，方便快速判断某个字符串是否在字典中。
  2. 定义 boolean[] dp，其中 dp[i] 表示 s 的前 i 个字符能否被拆分。
  3. 初始化 dp[0] = true，表示空字符串可以被拆分。
  4. 枚举字符串的结束位置 i。
  5. 对于每个 i，枚举切分点 j。
  6. 如果 dp[j] == true，并且 s.substring(j, i) 在字典中，说明 dp[i] = true。
  7. 最终返回 dp[s.length()]。

3. 关键逻辑

状态定义：

dp[i] 表示 s 的前 i 个字符能否被字典中的单词拼接出来

初始化：

dp[0] = true;

因为空字符串不需要任何单词，也可以认为是可以被成功拆分的。

状态转移：

if (dp[j] && set.contains(s.substring(j, i))) {
    dp[i] = true;
}

含义是：

  • 如果 dp[j] == true，说明 s 的前 j 个字符可以被拆分。
  • 如果 s.substring(j, i) 在字典中，说明从 j 到 i - 1 这一段可以作为一个单词。
  • 两部分都满足时，说明 s 的前 i 个字符可以被拆分。
  • 最终返回 dp[n]。

以 s = "leetcode" 为例：

wordDict = ["leet", "code"]

初始状态：

dp[0] = true

当 i = 4 时：

s.substring(0, 4) = "leet"

"leet" 在字典中，并且 dp[0] = true，所以：

dp[4] = true

当 i = 8 时：

j = 4
dp[4] = true
s.substring(4, 8) = "code"

"code" 在字典中，所以：

dp[8] = true

最终返回：

dp[8] = true

三、代码

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1. 处理特殊情况
        if (s == null || s.length() == 0) {
            return true;
        }

        // 2. 定义变量
        int n = s.length();

        // 将字典放入 HashSet，方便快速判断某个单词是否存在
        Set<String> set = new HashSet<>(wordDict);

        // dp[i] 表示 s 的前 i 个字符能否被字典中的单词拼接出来
        boolean[] dp = new boolean[n + 1];

        // 空字符串可以被拼接出来
        dp[0] = true;

        // 3. 核心逻辑
        // 枚举字符串的结束位置 i
        for (int i = 1; i <= n; i++) {
            // 枚举切分点 j
            for (int j = 0; j < i; j++) {
                // 如果 s 的前 j 个字符可以被拆分
                // 并且 s[j...i-1] 是字典中的单词
                // 那么 s 的前 i 个字符也可以被拆分
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        // 4. 返回结果
        return dp[n];
    }
}

四、复杂度分析

时间复杂度：O(n2)O(n^2)

说明：其中 n 是字符串 s 的长度。

外层循环枚举结束位置 i，内层循环枚举切分点 j，所以整体是双重循环，时间复杂度为 O(n2)O(n^2)。

如果严格考虑 Java 中 substring 创建字符串的开销，最坏情况下可能达到 O(n3)O(n^3)。

空间复杂度：O(n)O(n)

说明：使用了一个长度为 n + 1 的 dp 数组。

另外使用了一个 HashSet 存储字典单词，空间复杂度与字典大小有关。

评论