您现在的位置是:首页 >技术交流 >LeetCode 1048. Longest String Chain【记忆化搜索,动态规划,哈希表,字符串】中等网站首页技术交流
LeetCode 1048. Longest String Chain【记忆化搜索,动态规划,哈希表,字符串】中等
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
给出一个单词数组 words
,其中每个单词都由小写英文字母组成。如果我们可以 不改变其他字符的顺序 ,在 wordA
的任何地方添加 恰好一个 字母使其变成 wordB
,那么我们认为 wordA
是 wordB
的 前身 。
- 例如,
"abc"
是"abac"
的 前身 ,而"cba"
不是"bcad"
的 前身
词链是单词 [word_1, word_2, ..., word_k]
组成的序列,k >= 1
,其中 word1
是 word2
的前身,word2
是 word3
的前身,依此类推。一个单词通常是 k == 1
的 单词链 。从给定单词列表 words
中选择单词组成词链,返回 词链的 最长可能长度 。
示例 1:
输入:words = ["a","b","ba","bca","bda","bdca"]
输出:4
解释:最长单词链之一为 ["a","ba","bda","bdca"]
示例 2:
输入:words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出:5
解释:所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
示例 3:
输入:words = ["abcd","dbqca"]
输出:1
解释:字链["abcd"]是最长的字链之一。
["abcd","dbqca"]不是一个有效的单词链,因为字母的顺序被改变了。
提示:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i]
仅由小写英文字母组成。
解法1 记忆化搜索+哈希表
对于字符串 s s s 来说,假设它是词链的最后一个单词,那么去掉 s s s 中的一个字母,设新字符串为 t t t ,问题就变成计算以 t t t 结尾的词链的最长长度。由于这是一个和原问题相似的子问题,因此可以用递归解决。
直接把字符串作为递归的参数,定义
d
f
s
(
s
)
dfs(s)
dfs(s) 表示以
s
s
s 结尾的词链的最长长度。由于字符串的长度不超过
16
16
16 ,暴力枚举去掉的字符,设新字符串为
t
t
t 且在
w
o
r
d
s
words
words 中,则有
dfs
(
s
)
=
max
{
dfs
(
t
)
}
+
1
extit{dfs}(s) = max{ extit{dfs}(t)} + 1
dfs(s)=max{dfs(t)}+1
为了快速判断字符串是否在
w
o
r
d
s
words
words 中,需要将所有
words
[
i
]
extit{words}[i]
words[i] 存入哈希表
w
s
ws
ws 中。
由于 "aba"
和 "aca"
去掉中间字母都会变成 "aa"
,为避免重复计算,代码实现时可以用记忆化搜索。进一步地,可以直接把计算结果存到
w
s
ws
ws 中。(Python 可以使用 @cache
)
class Solution {
private Map<String, Integer> ws = new HashMap<>();
public int longestStrChain(String[] words) {
for (var s : words) ws.put(s, 0); // 0表示未被计算
int ans = 0;
for (var s : ws.keySet())
ans = Math.max(ans, dfs(s));
return ans;
}
private int dfs(String s) { // dfs(s)表示以s为最后一个单词的链的最长长度
int res = ws.get(s);
if (res > 0) return res; // 之前计算过
for (int i = 0; i < s.length(); ++i) { // 枚举去掉s[i]
var t = s.substring(0, i) + s.substring(i + 1);
if (ws.containsKey(t)) // t在words中
res = Math.max(res, dfs(t));
}
ws.put(s, res + 1); // 记忆化
return res + 1;
}
}
复杂度分析:
- 时间复杂度: O ( n L 2 ) mathcal{O}(nL^2) O(nL2) ,其中 n n n 为 w o r d s words words 的长度, L L L 为字符串的最大长度,本题不超过 16 16 16 。动态规划的时间复杂度 = 状态个数 × imes × 单个状态的计算时间。这里状态个数为 O ( n ) mathcal{O}(n) O(n) ,单个状态的计算时间为 O ( L 2 ) mathcal{O}(L^2) O(L2),因此时间复杂度为 O ( n L 2 ) mathcal{O}(nL^2) O(nL2) 。
- 空间复杂度: O ( n L ) mathcal{O}(nL) O(nL) 。每个状态都需要 O ( L ) mathcal{O}(L) O(L) 的空间。
解法2 动态规划——1:1 翻译成递推
我们可以去掉递归中的「递」,只保留「归」的部分,即自底向上计算。对于本题,只需要把递归改成循环。由于总是从短的字符串转移到长的字符串,所以要先把字符串按长度从小到大排序,然后从短的开始递推。
class Solution {
private Map<String, Integer> ws = new HashMap<>();
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
int ans = 0;
for (var s : words) {
int res = 0;
for (int i = 0; i < s.length(); ++i) { // 枚举去掉s[i]
var t = s.substring(0, i) + s.substring(i + 1);
res = Math.max(res, ws.getOrDefault(t, 0));
}
ws.put(s, res + 1);
ans = Math.max(ans, res + 1);
}
return ans;
}
}
复杂度分析:
- 时间复杂度: O ( n log n + n L 2 ) mathcal{O}(nlog n + nL^2) O(nlogn+nL2) ,其中 n n n 为 w o r d s words words 的长度, L L L 为字符串的最大长度,本题不超过 16 16 16 。排序的时间复杂度为 O ( n log n ) mathcal{O}(nlog n) O(nlogn)(注意只比较长度)。动态规划的时间复杂度 = 状态个数 × imes × 单个状态的计算时间,这里状态个数为 O ( n ) mathcal{O}(n) O(n) ,单个状态的计算时间为 O ( L 2 ) mathcal{O}(L^2) O(L2) 。
- 空间复杂度: O ( n L ) mathcal{O}(nL) O(nL) 。每个状态都需要 O ( L ) mathcal{O}(L) O(L) 的空间。