class Solution {
public:
int longestStrChain(vector<string>& words) {
}
};
1048. 最长字符串链
给出一个单词数组 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 <= 10001 <= words[i].length <= 16words[i] 仅由小写英文字母组成。原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.3 MB, 提交时间: 2023-04-27 09:19:17
func longestStrChain(words []string) (ans int) {
sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
f := map[string]int{}
for _, s := range words {
res := 0
for i := range s { // 枚举去掉 s[i]
res = max(res, f[s[:i]+s[i+1:]])
}
f[s] = res + 1
ans = max(ans, res+1)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 39 ms, 内存消耗: 41.4 MB, 提交时间: 2023-04-27 09:19:05
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
int ans = 0;
var f = new HashMap<String, Integer>();
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, f.getOrDefault(t, 0));
}
f.put(s, res + 1);
ans = Math.max(ans, res + 1);
}
return ans;
}
}
python3 解法, 执行用时: 116 ms, 内存消耗: 15.4 MB, 提交时间: 2023-04-27 09:18:50
# 递推
class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
f = {}
for s in words:
res = 0
for i in range(len(s)): # 枚举去掉 s[i]
res = max(res, f.get(s[:i] + s[i + 1:], 0))
f[s] = res + 1
return max(f.values())
golang 解法, 执行用时: 24 ms, 内存消耗: 6.5 MB, 提交时间: 2023-04-27 09:18:32
func longestStrChain(words []string) (ans int) {
ws := map[string]int{}
for _, s := range words {
ws[s] = 0 // 0 表示未被计算
}
var dfs func(string) int
dfs = func(s string) int {
res := ws[s]
if res > 0 { // 之前计算过
return res
}
for i := range s { // 枚举去掉 s[i]
t := s[:i] + s[i+1:]
if _, ok := ws[t]; ok {
res = max(res, dfs(t))
}
}
ws[s] = res + 1 // 记忆化
return res + 1
}
for s := range ws {
ans = max(ans, dfs(s))
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 32 ms, 内存消耗: 41.5 MB, 提交时间: 2023-04-27 09:18:18
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) {
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;
}
}
python3 解法, 执行用时: 100 ms, 内存消耗: 19 MB, 提交时间: 2023-04-27 09:18:02
# 记忆化搜索
class Solution:
def longestStrChain(self, words: List[str]) -> int:
ws = set(words)
@cache # 缓存装饰器，避免重复计算 dfs 的结果
def dfs(s: str) -> int:
res = 0
for i in range(len(s)): # 枚举去掉 s[i]
t = s[:i] + s[i + 1:]
if t in ws: # t 在 words 中
res = max(res, dfs(t))
return res + 1
return max(dfs(s) for s in ws)