【常见题型总结】序列 DP 模板题(总结「线性 DP」和「序列 DP」本质区别)
题目描述
这是 LeetCode 上的「139. 单词拆分」,难度为「中等」。
Tag : 「动态规划」、「哈希表」、「序列 DP」
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。请你判断是否可以利用字典中出现的单词拼接出 s
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 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
提示:
s
和wordDict[i]
仅有小写英文字母组成wordDict
中的所有字符串 互不相同
序列 DP
将字符串 s
长度记为
,wordDict
长度记为
。为了方便,我们调整字符串 s
以及将要用到的动规数组的下标从
开始。
定义
为考虑前
个字符,能否使用 wordDict
拼凑出来:当
代表
能够使用 wordDict
所拼凑,反之则不能。
不失一般性考虑
该如何转移:由于
需要考虑
范围内的字符,若
为 True
说明整个
都能够使用 wordDict
拼凑,自然也包括最后一个字符
所在字符串 sub
。
我们可以枚举最后一个字符所在字符串的左端点
,若
在 wordDict
中出现过,并且
,说明
能够被拼凑,并且子串 sub
也在 wordDict
,可得 f[i] = True
。
为了快速判断某个字符是否在 wordDict
中出现,我们可以使用 Set
结构对
进行转存。
Java 代码:
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
for (String word : wordDict) set.add(word);
int n = s.length();
boolean[] f = new boolean[n + 10];
f[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i && !f[i]; j++) {
String sub = s.substring(j - 1, i);
if (set.contains(sub)) f[i] = f[j - 1];
}
}
return f[n];
}
}
TypeScript 代码:
function wordBreak(s: string, wordDict: string[]): boolean {
const ss = new Set<string>(wordDict)
const n = s.length
const f = new Array<boolean>(n + 10).fill(false)
f[0] = true
for (let i = 1; i <= n; i++) {
for (let j = i; j >= 1 && !f[i]; j--) {
const sub = s.substring(j - 1, i)
if (ss.has(sub)) f[i] = f[j - 1]
}
}
return f[n]
}
Python 代码:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
ss = set(wordDict)
n = len(s)
f = [False] * (n + 10)
f[0] = True
for i in range(1, n + 1):
j = i
while j >= 1 and not f[i]:
sub = s[j - 1:i]
if sub in ss:
f[i] = f[j - 1]
j -= 1
return f[n]
- 时间复杂度:将
wordDict
转存在Set
复杂度为
;DP
过程复忽裁剪子串和查询 Set
结构的常数,复杂度为
- 空间复杂度:
总结
这里简单说下「线性 DP」和「序列 DP」的区别。
线性 DP 通常强调「状态转移所依赖的前驱状态」是由给定数组所提供的,即拓扑序是由原数组直接给出。更大白话来说就是通常有
依赖于
。
这就限定了线性 DP 的复杂度是简单由「状态数量(或者说是维度数)」所决定。
序列 DP 通常需要结合题意来寻找前驱状态,即需要自身寻找拓扑序关系(例如本题,需要自己通过枚举的方式来找左端点,从而找到可转移的前驱状态
)。
这就限定了序列 DP 的复杂度是由「状态数 + 找前驱」的复杂度所共同决定。也直接导致了序列 DP 有很多玩法,往往能够结合其他知识点出题,来优化找前驱这一操作,通常是利用某些性质,或是利用数据结构进行优化。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.139
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
相关文章
- Mac OSX 安装 MongoDB
- Kali Linux 在VMware Workstation Pro上的安装
- Kali Linux 配置下载源
- Linux安装JDK1.8
- Git 大闸蟹
- 搭建代码私有仓库-GitLab(CentOS-7||CentOS-7.1708)
- 分享一个好用的Linux连接工具 MobaXterm
- 分享一个自带翻译的Linux系统连接工具 FinalShell
- 新版本 Kali Linux系统 如何切换到root用户,以及对root 用户重新设置密码
- Kali Linux(2021.2)系统 安装中文输入法
- KaliLinux(2021.2) 系统如何切换中文语言
- KaliLinux-常用命令-进程-命令
- KaliLinux-常用命令-服务-命令
- KaliLinux-MSF-常用命令
- KaliLinux-剪切板攻击-PasteJacker工具的安装
- CentOS7-命令-关闭selinux
- PHP内置协议(支持的协议和封装协议)
- phpStudy 2016搭建-pikachu靶场
- 信息收集-DNS域传送漏洞工具-KaliLinux系统自带(dnsenum、dig)
- Linux 下安装 Nginx