LeetCode 139. 单词拆分：小白也能看懂的动态规划解法

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

字典中的单词可以重复使用。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1 2	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

约束条件：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

思路分析：动态规划

这道题是典型的可以使用动态规划（Dynamic Programming, DP）解决的问题。当我们判断一个较长的字符串是否能被拆分时，其结果可以依赖于其较短的前缀子串是否能被拆分。这种具有"最优子结构"和"重叠子问题"特征的问题，通常是 DP 的用武之地。

1. 定义状态 (DP 数组)

我们定义一个布尔类型的数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符（即子串 s[0...i-1]，注意是长度为 i 的前缀）是否可以被成功拆分成字典中的单词。
数组的长度设为 n+1，其中 n 是字符串 s 的长度。

dp[0]：代表空字符串。我们定义它为 true，因为空字符串可以被"拆分"（不包含任何单词，或者说，它本身就是一个合法的拆分起点）。这是动态规划非常重要的初始条件或基本情况 (base case)。
dp[1]：代表 s[0...0] (即 s 的第一个字符组成的子串) 是否可以被拆分。
…
dp[i]：代表 s[0...i-1] (即 s 的前 i 个字符组成的子串) 是否可以被拆分。
dp[n]：代表 s[0...n-1] (即整个字符串 s) 是否可以被拆分。这就是我们最终要求的目标。

2. 状态转移方程

现在，我们来思考如何计算 dp[i] 的值。
要判断 s 的前 i 个字符 s[0...i-1] 能否被拆分，我们可以尝试将其拆分成两部分：
s[0...i-1] = s[0...j-1] + s[j...i-1]

其中，j 是一个分割点，0 <= j < i。

s[0...j-1]：这是字符串 s 的前 j 个字符。它能否被拆分，对应的是 dp[j] 的值。
s[j...i-1]：这是从索引 j 开始，到索引 i-1 结束的子串。我们需要判断这个子串本身是否存在于我们的 wordDict 字典中。

如果存在一个 j ( 0 <= j < i )，使得 dp[j] 为 true (即 s 的前 j 个字符可以被拆分)，并且子串 s[j...i-1] 是字典 wordDict 中的一个单词，那么我们就可以断定 s 的前 i 个字符 s[0...i-1] 是可以被成功拆分的。此时，dp[i] 就应该为 true。

所以，状态转移方程可以表示为：
dp[i] = OR (dp[j] && wordDict.contains(s[j...i-1])) 对于所有 0 <= j < i。

用更易懂的语言来说：dp[i] 为真，当且仅当，存在一个 j（j 在 0 和 i-1 之间），使得 dp[j] 为真，并且从 j 到 i-1 的那段子字符串 s[j:i] 正好是字典里的一个单词。

只要我们能找到任何一个这样的 j，dp[i] 就可以被设置为 true，然后我们就可以停止对当前 i 的检查（因为已经找到一种拆分方法了）。

3. 初始化

dp[0] = true：如前所述，这是基础情况。
dp 数组的其他所有元素（dp[1] 到 dp[n]）在开始计算前，可以默认为 false。

4. 遍历顺序

外层循环：我们需要计算 dp[1], dp[2], ..., dp[n]。所以 i 从 1 遍历到 n。
内层循环：对于每一个 dp[i]，我们需要尝试所有可能的分割点 j。所以 j 从 0 遍历到 i-1。

举个例子

让我们用 s = "leetcode", wordDict = ["leet", "code"] 来模拟一下：

n = 8 (字符串 “leetcode” 的长度)
dp 数组大小为 9 (dp[0] 到 dp[8])
wordDictSet = {"leet": true, "code": true} (为了快速查找，我们通常会把字典转成哈希集合)

初始化：
dp[0] = true
dp[1...8] 初始化为 false

计算 dp[i]:

i = 1 (s[0:1] = “l”):
- j = 0: dp[0] (true) && wordDictSet["l"] (false)
- dp[1] = false
i = 2 (s[0:2] = “le”):
- j = 0: dp[0] (true) && wordDictSet["le"] (false)
- j = 1: dp[1] (false) && wordDictSet["e"] (false)
- dp[2] = false
i = 3 (s[0:3] = “lee”):
- …
- dp[3] = false
i = 4 (s[0:4] = “leet”):
- j = 0: dp[0] (true) && wordDictSet["leet"] (true) -> 条件满足！
- dp[4] = true (跳出内层 j 的循环)
i = 5 (s[0:5] = “leetc”):
- j = 0: dp[0] (true) && wordDictSet["leetc"] (false)
- j = 1: dp[1] (false) && wordDictSet["eetc"] (false)
- …
- j = 4: dp[4] (true) && wordDictSet["c"] (false)
- dp[5] = false
… (以此类推)
i = 8 (s[0:8] = “leetcode”):
- j = 0: dp[0] (true) && wordDictSet["leetcode"] (false)
- j = 1: …
- …
- j = 4: dp[4] (true) && wordDictSet[s[4:8]] (wordDictSet["code"]) (true) -> 条件满足！
- dp[8] = true (跳出内层 j 的循环)

最终，我们得到 dp[8] = true，这就是题目的答案。

代码实现 (Go)

下面是使用 Go 语言实现的 wordBreak 函数，其中包含了详细的注释。

package main

// @lc app=leetcode.cn id=139 lang=golang
// [139] 单词拆分

// @lc code=start
func wordBreak(s string, wordDict []string) bool {
	// 1. 将词典转换为哈希集合，方便快速查找单词是否存在
	// wordDictSet 用于存储词典中的所有单词。
	// 键是单词本身，值是布尔类型的 true，表示该单词在字典中。
	// 使用 map (哈希表) 实现集合，可以使得查找单词的平均时间复杂度为 O(L)，其中 L 是单词长度。
	wordDictSet := make(map[string]bool)
	for _, word := range wordDict { // 遍历词典中的每个单词 word
		wordDictSet[word] = true // 将单词 word 添加到哈希集合中
	}

	n := len(s) // 获取输入字符串 s 的长度

	// 2. 定义 DP 数组
	// dp[i] 表示字符串 s 的前 i 个字符 (即子串 s[0...i-1]) 
	// 是否可以被词典中的单词成功拆分。
	// dp 数组的大小为 n+1，索引从 0 到 n。
	// dp[0] 对应空字符串。
	// dp[n] 对应整个字符串 s。
	dp := make([]bool, n+1)

	// 3. 初始化 DP 数组
	// dp[0] = true，因为空字符串总是可以被"拆分"的，这是动态规划的基础。
	dp[0] = true

	// 4. 状态转移：填充 DP 数组
	// 外层循环 i 从 1 到 n。dp[i] 对应 s 的前 i 个字符 (s[0...i-1])。
	for i := 1; i <= n; i++ {
		// 内层循环 j 从 0 到 i-1。j 是一个潜在的分割点。
		// 我们尝试将 s[0...i-1] 分割为 s[0...j-1] 和 s[j...i-1]。
		for j := 0; j < i; j++ {
			// s[j:i] 在 Go 中表示从索引 j (包含) 到索引 i (不包含) 的子串，
			// 也就是我们上面分析的 s[j...i-1]。
			// 检查两个条件：
			// 1. dp[j] is true: 字符串 s 的前 j 个字符 s[0...j-1] 可以被拆分。
			// 2. wordDictSet[s[j:i]] is true: 子串 s[j...i-1] 是字典中的一个单词。
			if dp[j] && wordDictSet[s[j:i]] {
				dp[i] = true // 如果两个条件都满足，则 s 的前 i 个字符 s[0...i-1] 可以被拆分。
				break        // 已经找到了一个有效的拆分方式，无需继续检查其他分割点 j，跳出内层循环。
			}
		}
	}

	// 5. 返回结果
	// dp[n] 存储了整个字符串 s (即 s[0...n-1]) 是否可以被拆分的结果。
	return dp[n]
}

// @lc code=end

复杂度分析

时间复杂度： O(n^3)
- 我们有两层嵌套循环：外层循环 i 从 1 到 n，内层循环 j 从 0 到 i-1。这部分是 O(n^2) 次迭代。
- 在内层循环中，我们执行了 s[j:i] 来获取子串，并在 wordDictSet 中查找它。
- 在 Go 中，字符串切片 s[j:i] 的操作本身是 O(1) 的，因为它创建的是一个指向原始字符串数据的视图，并不复制字符数据。
- 哈希表（map）查找一个字符串 key 的平均时间复杂度是 O(length of key)。在这里，key 是子串 s[j:i]，其长度最大可以达到 i，也就是 O(n)。
- 因此，内层循环中的操作 wordDictSet[s[j:i]] 最坏情况下是 O(n)。
- 所以总的时间复杂度是 O(n^2 * n) = O(n^3)。
- 更精确地写出推导过程：
  [ T(n) = \sum_{i=1}^{n} \sum_{j=0}^{i-1} O(i-j) ]
  其中 ( O(i-j) ) 是查找长度为 ( i-j ) 的子串的成本。
  [ T(n) = \sum_{i=1}^{n} \sum_{k=1}^{i} O(k) = \sum_{i=1}^{n} O(i^2) = O(n^3) ]
空间复杂度： O(n + M)
- dp 数组：需要 O(n) 的空间，其中 n 是字符串 s 的长度。
- wordDictSet 哈希集合：需要存储字典中的所有单词。如果字典中有 k 个单词，平均长度为 L，那么空间复杂度是 O(k * L)。在题目约束下，wordDict.length <= 1000, wordDict[i].length <= 20，所以 M 最大约为 1000 * 20。通常我们把这个表示为 O(M)，其中 M 是字典中所有字符的总数。
- 所以总空间复杂度是 O(n + M)。

关键收获

动态规划的识别：当问题可以分解为具有重叠性质的子问题，并且子问题的解可以用来构建原问题的解时，考虑使用动态规划。
DP 状态定义：清晰地定义 dp[i] 的含义至关重要。在这里，dp[i] 代表"字符串的前 i 个字符是否可分"。
Base Case (初始条件)：dp[0] = true 是本题 DP 能够正确递推的关键。
状态转移：仔细思考如何从已知的子问题解（例如 dp[j]）推导出当前问题解（例如 dp[i]）。
数据结构辅助：将 wordDict 转换为哈希集合 wordDictSet 是一个常见的优化技巧，可以将单词查找时间从 O(num_words_in_dict * word_length)（如果线性扫描列表）降低到平均 O(word_length)。

这道"单词拆分"问题是动态规划在字符串处理中的一个经典应用，理解它有助于掌握 DP 的基本思想。