题目描述
思路解析动画文字版
记住「按长度排序，删字符找前驱，dp[w]=max(dp[前驱]+1)」，下面每帧都在套它。
第一步:按单词长度从短到长排好序。这样处理到某个单词时，它所有可能的前驱(更短)都已经算过、躺在 dp 表里了。
轮到 "a"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
删掉第 0 位得到前驱 "空串"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
所有删法看完，"a" 的最长链确定为 1，记进 dp 表(高亮行)。它没有可用前驱，单独成链。全局答案现在是 1。
轮到 "b"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
删掉第 0 位得到前驱 "空串"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
所有删法看完，"b" 的最长链确定为 1，记进 dp 表(高亮行)。它没有可用前驱，单独成链。全局答案现在是 1。
轮到 "ba"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
删掉第 0 位得到前驱 "a"，它在 dp 表里(高亮行)值为 1。那 "ba" 能接在它后面，候选链长 1+1=2，刷新 best 到 2。
删掉第 1 位得到前驱 "b"，它在 dp 表里(高亮行)值为 1。那 "ba" 能接在它后面，候选链长 1+1=2，与当前 best 持平，best 不变。
所有删法看完，"ba" 的最长链确定为 2，记进 dp 表(高亮行)。它是接在 "a" 后面得来的。全局答案现在是 2。
轮到 "bca"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
删掉第 0 位得到前驱 "ca"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
删掉第 1 位得到前驱 "ba"，它在 dp 表里(高亮行)值为 2。那 "bca" 能接在它后面，候选链长 2+1=3，刷新 best 到 3。
删掉第 2 位得到前驱 "bc"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 3。
所有删法看完，"bca" 的最长链确定为 3，记进 dp 表(高亮行)。它是接在 "ba" 后面得来的。全局答案现在是 3。
轮到 "bda"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
删掉第 0 位得到前驱 "da"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
删掉第 1 位得到前驱 "ba"，它在 dp 表里(高亮行)值为 2。那 "bda" 能接在它后面，候选链长 2+1=3，刷新 best 到 3。
删掉第 2 位得到前驱 "bd"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 3。
所有删法看完，"bda" 的最长链确定为 3，记进 dp 表(高亮行)。它是接在 "ba" 后面得来的。全局答案现在是 3。
轮到 "bdca"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
删掉第 0 位得到前驱 "dca"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
删掉第 1 位得到前驱 "bca"，它在 dp 表里(高亮行)值为 3。那 "bdca" 能接在它后面，候选链长 3+1=4，刷新 best 到 4。
删掉第 2 位得到前驱 "bda"，它在 dp 表里(高亮行)值为 3。那 "bdca" 能接在它后面，候选链长 3+1=4，与当前 best 持平，best 不变。
删掉第 3 位得到前驱 "bdc"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 4。
所有删法看完，"bdca" 的最长链确定为 4，记进 dp 表(高亮行)。它是接在 "bca" 后面得来的。全局答案现在是 4。
6 个单词全部结算完。dp 表里最大的值是 4，对应链 a → ba → bca → bdca(bda 也能接出同样长 4 的链，任选一条)。整个过程:排序一次，每个单词删一遍字符查 dp 表，一路填表得到答案。
边界先想清:单词、无前驱关系、一条直链。
面试重点:讲清「删比加省」和与记忆化的等价。
参考代码
from typing import Listclass Solution: def longestStrChain(self, words: List[str]) -> int: words.sort(key=len) dp = {} ans = 0 for w in words: best = 1 for i in range(len(w)): best = max(best, dp.get(w[:i] + w[i+1:], 0) + 1) dp[w] = best ans = max(ans, best) return ans复杂度
- 时间：O(n·L²)，n 个单词，每个删 L 次、每次拼串 O(L)
- 空间：O(n·L)，Python/Java 的 dp 只存 n 个真实单词 O(n)；C++ 用 dp[前驱] 会把缺失前驱也以 0 插进 map，最坏多存 n·L 个候选，故按 O(n·L) 计
易错点
面试追问把动画讲成自己的话
追问为什么是「删字符找前驱」而不是「加字符找后继」？
追问能不能记忆化 DFS 代替排序+递推？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长公共子序列
LeetCode 1143 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题