LeetCode 题解工作台
最长字符串链
给出一个单词数组 words ，其中每个单词都由小写英文字母组成。 如果我们可以 不改变其他字符的顺序 ，在 word A 的任何地方添加 恰好一个 字母使其变成 word B ，那么我们认为 word A 是 word B 的 前身 。 例如， "abc" 是 "abac" 的 前身 ，而 "cb…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def longestStrChain(self, words: List[str]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给出一个单词数组 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]仅由小写英文字母组成。
解题思路
方法一
class Solution:
def longestStrChain(self, words: List[str]) -> int:
def check(w1, w2):
if len(w2) - len(w1) != 1:
return False
i = j = cnt = 0
while i < len(w1) and j < len(w2):
if w1[i] != w2[j]:
cnt += 1
else:
i += 1
j += 1
return cnt < 2 and i == len(w1)
n = len(words)
dp = [1] * (n + 1)
words.sort(key=lambda x: len(x))
res = 1
for i in range(1, n):
for j in range(i):
if check(words[j], words[i]):
dp[i] = max(dp[i], dp[j] + 1)
res = max(res, dp[i])
return res
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N * L^2), where N is the number of words and L is the maximum word length, since each word can generate up to L predecessor candidates. Space complexity is O(N * L) for storing words in the hash map and their chain lengths. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask why we delete characters instead of inserting them during chain building.
- question_mark
Expect discussion on time-space trade-offs using hash maps versus dynamic programming arrays.
- question_mark
Clarify handling of words with the same length but different character order to avoid invalid chains.
常见陷阱
外企场景- error
Failing to sort words by length, which can lead to incorrect predecessor evaluation.
- error
Using insertion instead of deletion, which complicates finding valid predecessor words.
- error
Overwriting chain lengths without checking all predecessor candidates, missing longer chains.
进阶变体
外企场景- arrow_right_alt
Find all longest chains instead of just the length, returning sequences of words.
- arrow_right_alt
Modify constraints to allow uppercase letters and non-English alphabets, requiring extended hash handling.
- arrow_right_alt
Count the number of distinct longest chains instead of maximum length.