1048. 最长字符串链
题目描述
输入单词数组 words，每个单词由小写字母组成。
如果在单词 A 中某个位置插入恰好一个字母，并且不改动其他字母的顺序，就能得到单词 B，则称 A 是 B 的前身。例如 abc 是 abac 的前身，而 cba 不是 bcad 的前身。
单词链是一个序列 [w1, w2, ..., wk]（k >= 1），其中每个单词都是下一个单词的前身。单个单词本身也是长度为 1 的链。
从 words 中挑选单词组成单词链，返回链的最大可能长度。
示例 1
输入：words = ["a","b","ba","bca","bda","bdca"] 输出：4
解释：例如 a -> ba -> bda -> bdca，长度 4。
示例 2
输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] 输出：5
解释：五个单词能串成 xb -> xbc -> cxbc -> pcxbc -> pcxbcf。
示例 3
输入：words = ["abcd","dbqca"] 输出：1
解释：dbqca 中字母顺序与 abcd 不一致，无法相连，只能各自成链。
数据范围
1 <= words.length <= 10001 <= words[i].length <= 16words[i]只含小写英文字母。
解题思路
前身一定比后继短 1，所以按长度从短到长处理。设 dp[w] 为以 w 结尾的最长链长度。与其去找“谁能插一个字母变成 w”，不如反过来：依次删掉 w 的第 k 个字母得到 prev，如果 prev 在 dp 里，就能接上：dp[w] = max(dp[prev] + 1)；一个都没有则为 1。答案是所有 dp 的最大值。
为什么正确
处理 w 时，所有更短的单词都已在 dp 中且已是最优，而 w 的前身恰好都是删一个字母得到的字符串。
复杂度分析
时间 O(n log n + n·L²)（L 为单词长度，删字母生成字符串 O(L)），空间 O(n·L)。
易错点
必须先按长度排序，否则算 w 时它的前身可能还没算。不要按字典序排。前身可以在任意位置插字母，不只是末尾。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
dp = {}
ans = 0
for w in words:
best = 1
for k in range(len(w)):
prev = w[:k] + w[k + 1:]
if prev in dp:
best = max(best, dp[prev] + 1)
dp[w] = best
ans = max(ans, best)
return ansclass Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
Map<String, Integer> dp = new HashMap<>();
int ans = 0;
for (String w : words) {
int best = 1;
for (int k = 0; k < w.length(); k++) {
String prev = w.substring(0, k) + w.substring(k + 1);
if (dp.containsKey(prev)) {
best = Math.max(best, dp.get(prev) + 1);
}
}
dp.put(w, best);
ans = Math.max(ans, best);
}
return ans;
}
}class Solution {
public:
int longestStrChain(vector<string>& words) {
sort(words.begin(), words.end(), [](const string& a, const string& b) { return a.size() < b.size(); });
unordered_map<string, int> dp;
int ans = 0;
for (const string& w : words) {
int best = 1;
for (int k = 0; k < (int)w.size(); k++) {
string prev = w.substr(0, k) + w.substr(k + 1);
if (dp.count(prev)) {
best = max(best, dp[prev] + 1);
}
}
dp[w] = best;
ans = max(ans, best);
}
return ans;
}
};func longestStrChain(words []string) int {
sort.Slice(words, func(a, b int) bool { return len(words[a]) < len(words[b]) })
dp := map[string]int{}
ans := 0
for _, w := range words {
best := 1
for k := 0; k < len(w); k++ {
prev := w[:k] + w[k+1:]
if v, ok := dp[prev]; ok {
best = max(best, v+1)
}
}
dp[w] = best
ans = max(ans, best)
}
return ans
}var longestStrChain = function(words) {
words.sort((a, b) => a.length - b.length);
const dp = new Map();
let ans = 0;
for (const w of words) {
let best = 1;
for (let k = 0; k < w.length; k++) {
const prev = w.slice(0, k) + w.slice(k + 1);
if (dp.has(prev)) {
best = Math.max(best, dp.get(prev) + 1);
}
}
dp.set(w, best);
ans = Math.max(ans, best);
}
return ans;
};function longestStrChain(words: string[]): number {
words.sort((a, b) => a.length - b.length);
const dp = new Map<string, number>();
let ans = 0;
for (const w of words) {
let best = 1;
for (let k = 0; k < w.length; k++) {
const prev = w.slice(0, k) + w.slice(k + 1);
if (dp.has(prev)) {
best = Math.max(best, dp.get(prev)! + 1);
}
}
dp.set(w, best);
ans = Math.max(ans, best);
}
return ans;
}