LeetCode 1048: Longest String Chain (DP by Deleting One Character)
LeetCode 1048Dynamic ProgrammingHash TableToday we solve LeetCode 1048 - Longest String Chain.
Source: https://leetcode.com/problems/longest-string-chain/
English
Problem Summary
Given a list of words, a word A is a predecessor of B if we can insert exactly one character anywhere in A to get B. Return the length of the longest possible word chain.
Key Insight
If we sort words by length, then when processing a word w, all possible predecessors have length len(w)-1 and have already been processed. So we can use DP on words: dp[w] = 1 + max(dp[pred]) over all predecessors generated by deleting one character from w.
Algorithm
- Sort words by increasing length.
- For each word w, initialize best = 1.
- For every position i, create predecessor w[0:i] + w[i+1:].
- If predecessor exists in DP map, update best = max(best, dp[pred] + 1).
- Set dp[w] = best and maintain global answer.
Complexity Analysis
Let n be number of words and L be maximum word length.
Time: O(n log n + n · L²) (sorting + generating L predecessors each requiring substring construction).
Space: O(n) for the DP hash map.
Common Pitfalls
- Forgetting to sort by length, causing missing predecessor states.
- Trying only one delete position instead of all positions.
- Treating anagrams as chainable (order must be preserved except one inserted char).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, Comparator.comparingInt(String::length));
Map<String, Integer> dp = new HashMap<>();
int ans = 1;
for (String w : words) {
int best = 1;
for (int i = 0; i < w.length(); i++) {
String pred = w.substring(0, i) + w.substring(i + 1);
best = Math.max(best, dp.getOrDefault(pred, 0) + 1);
}
dp.put(w, best);
ans = Math.max(ans, best);
}
return ans;
}
}func longestStrChain(words []string) int {
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
dp := make(map[string]int, len(words))
ans := 1
for _, w := range words {
best := 1
for i := 0; i < len(w); i++ {
pred := w[:i] + w[i+1:]
if v, ok := dp[pred]; ok && v+1 > best {
best = v + 1
}
}
dp[w] = best
if best > ans {
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 = 1;
for (const string& w : words) {
int best = 1;
for (int i = 0; i < (int)w.size(); ++i) {
string pred = w.substr(0, i) + w.substr(i + 1);
auto it = dp.find(pred);
if (it != dp.end()) best = max(best, it->second + 1);
}
dp[w] = best;
ans = max(ans, best);
}
return ans;
}
};class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
dp = {}
ans = 1
for w in words:
best = 1
for i in range(len(w)):
pred = w[:i] + w[i + 1:]
best = max(best, dp.get(pred, 0) + 1)
dp[w] = best
ans = max(ans, best)
return ansvar longestStrChain = function(words) {
words.sort((a, b) => a.length - b.length);
const dp = new Map();
let ans = 1;
for (const w of words) {
let best = 1;
for (let i = 0; i < w.length; i++) {
const pred = w.slice(0, i) + w.slice(i + 1);
best = Math.max(best, (dp.get(pred) || 0) + 1);
}
dp.set(w, best);
ans = Math.max(ans, best);
}
return ans;
};中文
题目概述
给定一个单词数组。若单词 A 通过在任意位置插入一个字符可以变成 B，则 A 是 B 的前驱。求最长字符串链长度。
核心思路
按单词长度从小到大排序。处理当前单词 w 时，它的所有前驱都应是长度 len(w)-1，并且已经处理过。于是可做哈希 DP：dp[w] = 1 + max(dp[pred])，其中 pred 是删除 w 某一位字符得到的字符串。
算法步骤
- 先按长度升序排序。
- 对每个单词 w，初值 best=1。
- 枚举删除位置 i，构造 pred = w[:i] + w[i+1:]。
- 若 pred 在 DP 中，更新 best = max(best, dp[pred] + 1)。
- 记录 dp[w] = best，并更新全局答案。
复杂度分析
设单词数为 n，最大长度为 L。
时间复杂度：O(n log n + n · L²)。
空间复杂度：O(n)。
常见陷阱
- 没有按长度排序，导致前驱状态未准备好。
- 删除字符时只尝试一个位置，漏掉其他合法前驱。
- 误把“字母集合相同”当成可链，实际必须保持相对顺序。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, Comparator.comparingInt(String::length));
Map<String, Integer> dp = new HashMap<>();
int ans = 1;
for (String w : words) {
int best = 1;
for (int i = 0; i < w.length(); i++) {
String pred = w.substring(0, i) + w.substring(i + 1);
best = Math.max(best, dp.getOrDefault(pred, 0) + 1);
}
dp.put(w, best);
ans = Math.max(ans, best);
}
return ans;
}
}func longestStrChain(words []string) int {
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
dp := make(map[string]int, len(words))
ans := 1
for _, w := range words {
best := 1
for i := 0; i < len(w); i++ {
pred := w[:i] + w[i+1:]
if v, ok := dp[pred]; ok && v+1 > best {
best = v + 1
}
}
dp[w] = best
if best > ans {
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 = 1;
for (const string& w : words) {
int best = 1;
for (int i = 0; i < (int)w.size(); ++i) {
string pred = w.substr(0, i) + w.substr(i + 1);
auto it = dp.find(pred);
if (it != dp.end()) best = max(best, it->second + 1);
}
dp[w] = best;
ans = max(ans, best);
}
return ans;
}
};class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
dp = {}
ans = 1
for w in words:
best = 1
for i in range(len(w)):
pred = w[:i] + w[i + 1:]
best = max(best, dp.get(pred, 0) + 1)
dp[w] = best
ans = max(ans, best)
return ansvar longestStrChain = function(words) {
words.sort((a, b) => a.length - b.length);
const dp = new Map();
let ans = 1;
for (const w of words) {
let best = 1;
for (let i = 0; i < w.length; i++) {
const pred = w.slice(0, i) + w.slice(i + 1);
best = Math.max(best, (dp.get(pred) || 0) + 1);
}
dp.set(w, best);
ans = Math.max(ans, best);
}
return ans;
};
Comments