最长字符串链 图解题解
这道题到底在问什么
- 输入
- words=["a","b","ba","bca","bda","bdca"]
- 输出
- 4 （如 a → ba → bca → bdca；bda 也能接出等长链）
最优解：一步一步想明白
- 3记住「按长度排序，删字符找前驱，dp[w]=max(dp[前驱]+1)」，下面每帧都在套它。
- 4第一步:按单词长度从短到长排好序。这样处理到某个单词时，它所有可能的前驱(更短)都已经算过、躺在 dp 表里了。
- 5轮到 "a"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
- 6删掉第 0 位得到前驱 "空串"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
- 7所有删法看完，"a" 的最长链确定为 1，记进 dp 表(高亮行)。它没有可用前驱，单独成链。全局答案现在是 1。
- 8轮到 "b"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
- 9删掉第 0 位得到前驱 "空串"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
- 10所有删法看完，"b" 的最长链确定为 1，记进 dp 表(高亮行)。它没有可用前驱，单独成链。全局答案现在是 1。
- 11轮到 "ba"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
- 12删掉第 0 位得到前驱 "a"，它在 dp 表里(高亮行)值为 1。那 "ba" 能接在它后面，候选链长 1+1=2，刷新 best 到 2。
- 13删掉第 1 位得到前驱 "b"，它在 dp 表里(高亮行)值为 1。那 "ba" 能接在它后面，候选链长 1+1=2，与当前 best 持平，best 不变。
- 14所有删法看完，"ba" 的最长链确定为 2，记进 dp 表(高亮行)。它是接在 "a" 后面得来的。全局答案现在是 2。
- 15轮到 "bca"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
- 16删掉第 0 位得到前驱 "ca"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
- 17删掉第 1 位得到前驱 "ba"，它在 dp 表里(高亮行)值为 2。那 "bca" 能接在它后面，候选链长 2+1=3，刷新 best 到 3。
- 18删掉第 2 位得到前驱 "bc"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 3。
- 19所有删法看完，"bca" 的最长链确定为 3，记进 dp 表(高亮行)。它是接在 "ba" 后面得来的。全局答案现在是 3。
- 20轮到 "bda"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
- 21删掉第 0 位得到前驱 "da"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
- 22删掉第 1 位得到前驱 "ba"，它在 dp 表里(高亮行)值为 2。那 "bda" 能接在它后面，候选链长 2+1=3，刷新 best 到 3。
- 23删掉第 2 位得到前驱 "bd"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 3。
- 24所有删法看完，"bda" 的最长链确定为 3，记进 dp 表(高亮行)。它是接在 "ba" 后面得来的。全局答案现在是 3。
- 25轮到 "bdca"。先给它一个保底值 best = 1(自己单独成一条链)。接着逐位删一个字母，看能不能接到某个已知前驱后面。
- 26删掉第 0 位得到前驱 "dca"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 1。
- 27删掉第 1 位得到前驱 "bca"，它在 dp 表里(高亮行)值为 3。那 "bdca" 能接在它后面，候选链长 3+1=4，刷新 best 到 4。
- 28删掉第 2 位得到前驱 "bda"，它在 dp 表里(高亮行)值为 3。那 "bdca" 能接在它后面，候选链长 3+1=4，与当前 best 持平，best 不变。
- 29删掉第 3 位得到前驱 "bdc"，它不在 dp 表里(不是给定单词)，接不上，跳过。best 仍是 4。
- 30所有删法看完，"bdca" 的最长链确定为 4，记进 dp 表(高亮行)。它是接在 "bca" 后面得来的。全局答案现在是 4。
- 316 个单词全部结算完。dp 表里最大的值是 4，对应链 a → ba → bca → bdca(bda 也能接出同样长 4 的链，任选一条)。整个过程:排序一次，每个单词删一遍字符查 dp 表，一路填表得到答案。
⚠️ 容易写错的地方
✗ 错：不排序直接 DP
✓ 对：必须先按长度升序排序
处理 w 时要求所有更短的前驱已经算好；不排序前驱可能还没填进 dp
✗ 错：把缺失前驱的默认 0 当成有效链长
✓ 对：只有 dp 里真实出现的前驱才算接得上
链上每一环都得是 words 中的真实单词。缺失前驱取默认 0、0+1=1 恰好等于保底 best，所以即便代码不显式判存在(如 C++ dp[前驱])结果也对，但别误以为真接上了某条链
✗ 错：best 初值设 0
✓ 对：best 初值设 1
每个单词至少能自己单独成一条长度为 1 的链
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 ansC++
#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
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 (auto &w : words) {
int best = 1;
for (int i = 0; i < (int)w.size(); ++i) best = max(best, dp[w.substr(0,i) + w.substr(i+1)] + 1);
dp[w] = best;
ans = max(ans, best);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, Comparator.comparingInt(String::length));
Map<String, Integer> dp = new HashMap<>();
int ans = 0;
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;
}
}复杂度
时间
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) 计
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长字符串链 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是「删字符找前驱」而不是「加字符找后继」？+
从后继 w 删一个字符，候选只有 L 个(每个位置一种)，且都比 w 短，凡其中是给定单词的早已在 dp 表里、直接查；不是给定单词的查不到、跳过。若反过来枚举加字符的后继，每个位置可加 26 种字母、共 26·L 个候选，还都比 w 长(尚未处理)，复杂度更高也更难对齐 DP 顺序。
能不能记忆化 DFS 代替排序+递推？+
可以。dfs(w) 枚举删一字符的前驱递归取 max+1，用 dp 缓存。本质同一棵依赖图，时间也是 O(n·L²)；排序递推写法更直观、无递归栈开销。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最长字符串链 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。