type
Post
status
Published
date
Jul 26, 2022
slug
leetcode-139-word-break
summary
tags
动态规划
字符串哈希
category
LeetCode热题HOT100
icon
password
一、题目链接
二、题解
反向思维？
问题是问能够用 wordDict 中的单词拼接成 s 字符串，但是我们应该反着想，是否可以将 s 字符串拆分成若干个字符串，使得拆分出来的字符串都在 wordDict 中即可！
字符串哈希
由于使用自带的哈希表，哈希查询字符串时的复杂度最坏是和字符串长度成正比的，即 ，因此整个算法复杂度最坏会升级到 ，因此可以使用字符串哈希将其降到
动态规划
- 状态表示：f[i] 表示 s 串的 [1, i] 是否可以拆分为 wordDict 中的字符串
- 状态计算：考虑拆分的最后一步，最后一步可以拆分到 j 的位置, 使得区间变为 [1, j] 和 [j + 1, i]
- 所以：f[i] = f[j] & s[j + 1, i] 在wordDict中
- 初始状态：保证代码正确性，f[0] = true，无特别意义或者可以理解为 s 串的 [0, 0] 可以拆分为 wordDict 中的字符串（即都为空串）
- 最终答案：f[n] 表示 s[1, n] 是否可以拆分为 wordDict 中的字符串
复杂度分析
- 时间复杂度：
- 空间复杂度：
三、代码实现
- 作者:NotionNext
- 链接:https://tangly1024.com/article/leetcode-139-word-break
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。