最长字符串链 图解题解

最长字符串链这道题到底在接什么

给一堆单词 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。

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 ans

C++

#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;
    }
}