题目描述
思路解析
一句话答案：LeetCode 1048 最长字符串链：先按长度排序保证前驱先算，dp[w] 记以 w 结尾的最长链，逐位删一个字母拼出前驱、查哈希表取 dp[前驱]+1 的最大值。删比两两比较省，时间 O(n·L²)，空间 O(n·L)。
最长字符串链这道题到底在接什么
给一堆单词 words，若在单词 a 里任意位置插入一个字母能得到 b，就说 a 是 b 的前驱。要找一条尽量长的词链：链上每个词都是下一个词的前驱，返回最长链的长度。以 words=["a","b","ba","bca","bda","bdca"] 为例，「a」→「ba」→「bca」→「bdca」串成一条，长度 4。
为什么两两配对判前驱会越接越慢
想连成链，把 n 个词两两配对判谁能接谁——n² 对组合，判一对前驱还得逐字符比差没差一个字母，又是 O(L)（L 是单词长度，大 O 记号说的是规模变大时操作数怎么涨）。找最长链时短链还会被不同长词反复走。
换成删字母查表，dp 存的是每个词结尾的最长链
能接在 w 前面的前驱，一定是 w 删掉某一个字母得来的——比 w 短一个字母，插回去正好是 w。于是不必两两比，只要逐位删掉 w 一个字母、拼出前驱查表。用哈希表（把键直接映射到值、查一次几乎不花时间）dp 存「单词 → 以它结尾的最长链长度」；把『以每个词结尾的最长链』算一次存下、后面删字母查表直接取，就是动态规划。
查 dp 时前驱得已算好：前驱总比当前词短，先按长度从短到长排序，轮到某词时更短的都已算过、躺在 dp 里。
dp[w] 为什么是删出来的前驱里取最大再加一
定义 dp[w] 为以 w 结尾的最长链长度（后面更长的词删字母查到它就直接取）。先给 w 保底 best=1：它至少自成一条链。再逐位删一个字母得候选前驱，若前驱在 dp 里就把 w 接上去、链长 dp[前驱]+1；dp[w] 取 best 与各个 dp[前驱]+1 里的最大值。
删出的要是没人认的乱串，它不在 dp 里、按 0 算，0+1=1 超不过保底。每个词填一遍、刷新全局最大值就是答案。删一个字母只有 L 种删法，这就是删比加省。
拿题面六个单词亲手把 dp 填一遍
先按长度排好，顺序是 「a」、「b」、「ba」、「bca」、「bda」、「bdca」。「a」「b」删出空串、接不上，dp 各记 1。「ba」：删得 「a」值 1、候选 1+1=2，best 到 2，删 「b」持平，dp 记 2。「bca」：删得 「ca」「bc」都不在、「ba」值 2 候选 3，dp 记 3。「bda」同理靠 「ba」接出 3。「bdca」：删得 「bca」值 3、候选 4，「bda」值 3 持平，另两种不在，dp 记 4。
六个词填完，dp 里最大是 4，对上题面答案。
不排序，bca 先于 ba 处理，链为什么会断
时间上，排序 O(n log n)，主循环每个词删 L 次、每次拼长约 L 的前驱串查表 O(L)，合起来 O(n·L²)；本题 L≤16 很小。空间存 n 个单词的 dp，按 O(n·L) 计。
最容易砸在排序上：删字母查表默认前驱早算好，可要是 「bca」 排在 「ba」 前头，查 「ba」 时表里还没它，链断在半路、答案偏小——排序让前驱先进表是整套做法的地基。另一处是保底值：每个词起手 best 得是 1（自成一条长度 1 的链），写成 0，孤立词会算成 0，可它本该记 1。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「按长度排序，删字符找前驱，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 1105 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题