LC 139. 单词拆分
题目描述
这是 LeetCode 上的 139. 单词拆分 ,难度为 中等。
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。请你判断是否可以利用字典中出现的单词拼接出 s
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
提示:
- $1 <= s.length <= 300$
- $1 <= wordDict.length <= 1000$
- $1 <= wordDict[i].length <= 20$
s
和wordDict[i]
仅有小写英文字母组成wordDict
中的所有字符串 互不相同
序列 DP
将字符串 s
长度记为 $n$,wordDict
长度记为 $m$。为了方便,我们调整字符串 s
以及将要用到的动规数组的下标从 $1$ 开始。
定义 $f[i]$ 为考虑前 $i$ 个字符,能否使用 wordDict
拼凑出来:当 $f[i] = true$ 代表 $s[1…i]$ 能够使用 wordDict
所拼凑,反之则不能。
不失一般性考虑 $f[i]$ 该如何转移:由于 $f[i]$ 需要考虑 $s[1…i]$ 范围内的字符,若 $f[i]$ 为 True
说明整个 $s[1…i]$ 都能够使用 wordDict
拼凑,自然也包括最后一个字符 $s[i]$ 所在字符串 sub
。
我们可以枚举最后一个字符所在字符串的左端点 $j$,若 $sub = s[j…i]$ 在 wordDict
中出现过,并且 $f[j - 1] = True$,说明 $s[0…(j - 1)]$ 能够被拼凑,并且子串 sub
也在 wordDict
,可得 f[i] = True
。
为了快速判断某个字符是否在 wordDict
中出现,我们可以使用 Set
结构对 $wordDict[i]$ 进行转存。
Java 代码:
1 |
|
C++ 代码:
1 |
|
Python 代码:
1 |
|
TypeScript 代码:
1 |
|
- 时间复杂度:将
wordDict
转存在Set
复杂度为 $O(m)$;DP
过程复忽裁剪子串和查询Set
结构的常数,复杂度为 $O(n^2)$ - 空间复杂度:$O(n + m)$
总结
这里简单说下「线性 DP」和「序列 DP」的区别。
线性 DP 通常强调「状态转移所依赖的前驱状态」是由给定数组所提供的,即拓扑序是由原数组直接给出。更大白话来说就是通常有 $f[i][…]$ 依赖于 $f[i - 1][…]$。
这就限定了线性 DP 的复杂度是简单由「状态数量(或者说是维度数)」所决定。
序列 DP 通常需要结合题意来寻找前驱状态,即需要自身寻找拓扑序关系(例如本题,需要自己通过枚举的方式来找左端点,从而找到可转移的前驱状态 $f[j - 1]$)。
这就限定了序列 DP 的复杂度是由「状态数 + 找前驱」的复杂度所共同决定。也直接导致了序列 DP 有很多玩法,往往能够结合其他知识点出题,来优化找前驱这一操作,通常是利用某些性质,或是利用数据结构进行优化。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.139
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!