110.单词拆分
题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
- 输入: s = "leetcode", wordDict = ["leet", "code"]
- 输出: true
- 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
- 输入: s = "applepenapple", wordDict = ["apple", "pen"]
- 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
- 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
- 输出: false
思路
核心思路：逐段判断，用备忘录
想象你手里有一张纸条，上面写着一句话。你要判断这句话能不能由字典里的词拼出来。你会怎么做？
最直观的方法：从左往右看，找到一个在字典里的词，切掉它，然后继续看剩下的部分能不能拼出来。如果某次切掉后剩下的部分也能拼出来，就成功了。
但这种方法会有很多重复判断（比如同一个子串被多次检查），所以我们需要记录每个子串是否可行，避免重复计算。
动态规划思想
我们定义一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符（即 s[0..i-1]）能否被成功拆分。
初始状态：dp[0] = true，表示空字符串是可以拆分的（不取任何单词）。
状态转移：对于每个 i（从 1 到 s.length()），我们尝试找一个分割点 j（0 <= j < i），使得： - dp[j] = true（前 j 个字符可以被拆分） - 并且子串 s[j..i-1]（即从第 j 个字符到第 i-1 个字符）在字典中 如果存在这样的 j，那么 dp[i] = true。
最终答案：dp[s.length()]。
举个例子：s = "leetcode", dict = ["leet","code"] - 初始化 dp[0] = true。 - i = 1（检查前1个字符 "l"）：没有 j 使得子串在字典中 → dp[1] = false - i = 2 ("le")：false - i = 3 ("lee")：false - i = 4 ("leet")：j = 0 时，dp[0]=true，子串 s[0..3]="leet" 在字典中 → dp[4] = true - i = 5 ("leetc")：尝试 j = 4，dp[4]=true，子串 s[4..4]="c" 不在字典中；其他 j 都不行 → dp[5]=false - i = 6 ("leetco")：尝试 j = 4，子串 s[4..5]="co" 不在字典中 → false - i = 7 ("leetcod")：尝试 j = 4，子串 s[4..6]="cod" 不在字典中 → false - i = 8 ("leetcode")：尝试 j = 4，子串 s[4..7]="code" 在字典中，且 dp[4]=true → dp[8]=true 所以最终 dp[8]=true，可以拆分。
优化技巧
- 用 HashSet 存储字典：方便 O(1) 判断子串是否在字典中。
- 限制子串长度：我们可以先找出字典中最长单词的长度 maxLen，那么在检查子串时，子串长度不能超过 maxLen，这样- 可以减少不必要的循环。即 j 从 i - maxLen 到 i-1（且 j >= 0）。
- 剪枝：如果 dp[i] 已经为 true，可以提前跳出内层循环。
class Solution {
fun wordBreak(s: String, wordDict: List<String>): Boolean {
// 把字典放进集合里，查找一个单词在不在字典中会更快
val set = wordDict.toHashSet()
// dp[i] 表示：s 的前 i 个字符，能不能被拆分成功
val dp = BooleanArray(s.length + 1)
// 空字符串默认是可以拆分成功的
dp[0] = true
// i 表示前 i 个字符
for (i in 1..s.length) {
// 枚举最后一刀切在哪里
for (j in 0 until i) {
// 如果前 j 个字符已经能拆成功，
// 并且 s[j, i) 这一段正好是字典里的单词，
// 那么前 i 个字符也能拆成功
if (dp[j] && s.substring(j, i) in set) {
dp[i] = true
break // 跳出j循环，继续判断下一个i
}
}
}
return dp[s.length] # 最后一个字符都判断完，如果能切就可以
}
}
复杂度
- 时间复杂度: O(n² × L) 其中 n 是 s 的长度，L 是子串截取和哈希查找的平均时间（通常视为 O(1)），所以实际上是 O(n²)。加上最大长度优化后，平均复杂度降低。
- 空间复杂度: 空间复杂度：O(n + m)，n 是 dp 数组长度，m 是字典大小。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!