LeetCode 1048. 最长字符串链

2023-12-27 HGNULB 约 9 分钟

文章信息 7 个分类 6 个标签

分类

题目描述

✅ 1048. 最长字符串链

题意分析

题目先定义了一种「前身」关系：若在字符串 A 中的任意位置插入恰好一个字母就能得到字符串 B，且插入过程不改变 A 原有字符的相对顺序，则称 A 是 B 的前身。要求从给定的单词集合里挑出尽可能多的单词，排成一条每一项都是下一项前身的链，返回链的长度。

这个定义有一条不能忽略的推论：链上相邻两个单词的长度恰好相差 $1$，一个字符不多一个字符不少。所以整条链的长度被单词长度的跨度锁死，长度相同的两个单词之间永远不可能连边。

约束里单词数量不超过 $1000$，单个单词长度不超过 $16$，只含小写字母。长度上限 $16$ 是一个很显眼的信号：从一个单词出发往回退一步的候选只有十几种，这个数量小到可以逐一构造出来。

边界方面，单个单词自身就构成一条长度为 $1$ 的链，所以答案的下界是 $1$，不存在返回 $0$ 的情况。若所有单词长度都相同，任何两词之间都没有前身关系，答案就是 $1$。链上的单词不要求在原数组中相邻，也不要求用满所有单词，只需是一个子集。

解法：按长度排序的动态规划

核心思路

朴素做法是把每个单词看成图上的点，对所有单词两两判断是否构成前身关系，连边之后求最长路。判断一对单词是否相差一次插入需要扫一遍字符，总代价是 $O(n^2 L)$。瓶颈在于绝大多数单词对的长度根本不相差 $1$，这些配对从一开始就注定失败，却仍然被逐个检查了一遍。

换个方向想。与其从一个单词去「找」它的前身是谁，不如直接把前身「造」出来。既然前身一定是从当前单词删掉恰好一个字符得到的，那么删除位置只有 $L$ 种选择，构造出来的候选串最多 $L$ 个。把所有已处理的单词放进哈希表，拿这 $L$ 个候选串去查表，命中的就是真实存在的前身。这样两两配对的 $n^2$ 就被压成了 $n \cdot L$ 次查询。

状态定义为：dp[w] 表示以单词 w 作为结尾的最长词链长度。转移是 dp[w] = max(1, max{dp[pre] + 1})，其中 pre 取遍 w 删去一个字符得到的、且确实出现在集合中的串。取 $1$ 作为下界，对应「w 自己独占一条链」。

这个转移要成立，必须保证计算 dp[w] 时它的所有前身都已经算完。前身比 w 短一个字符，所以只要把单词按长度升序处理，就天然构成了一个合法的拓扑序，不需要显式建图也不需要记忆化递归。长度相同的单词之间没有依赖，它们内部的先后顺序可以任意。

解题步骤

先把 words 按长度从小到大排序。排序是整套逻辑的地基：它把「前身必须先于后继被计算」这个依赖关系转成了简单的遍历顺序，省去了建图和拓扑排序。

准备一张哈希表 dp，键是单词，值是以它结尾的最长链长。用哈希表而不是数组下标，是因为转移时手上只有构造出来的候选字符串，没有它在原数组中的位置。

按排序后的顺序遍历每个单词，先把当前链长 best 初始化为 $1$。这个初值代表单词自成一链，不能写成 $0$，否则孤立单词的答案会整体少 $1$。

对每个删除位置 i（从 $0$ 到 word.length() - 1，末位也必须包含），把前缀 word[0, i) 和后缀 word[i + 1, end) 拼起来得到候选前身 pre，用 dp[pre] + 1 去更新 best。查不到时按 $0$ 处理，0 + 1 = 1 恰好等于下界，不会污染结果，所以不需要额外的存在性判断。

把 best 写回 dp[word]，同时用它更新全局答案。必须在循环内维护全局最大值，因为最长链的终点不一定是排序后的最后一个单词。

以 words = ["a", "b", "ba", "bca", "bda", "bdca"] 走一遍：按长度排序后顺序为 a、b、ba、bca、bda、bdca（前两个长度都是 $1$，谁在前都不影响）。

处理 a：best 起始为 $1$，删掉唯一的字符得到空串，哈希表里没有，按 $0$ 算，best 仍为 $1$，写入 dp["a"] = 1，答案更新为 $1$。处理 b 同理，dp["b"] = 1。

处理 ba：删下标 $0$ 得到 "a"，查到 dp["a"] = 1，best 更新为 $2$；删下标 $1$ 得到 "b"，查到 $1$，best 仍为 $2$。写入 dp["ba"] = 2，答案更新为 $2$。

处理 bca：删下标 $0$ 得 "ca" 未命中；删下标 $1$ 得 "ba"，查到 $2$，best 更新为 $3$；删下标 $2$ 得 "bc" 未命中。写入 dp["bca"] = 3，答案更新为 $3$。处理 bda 完全对称，删下标 $1$ 得 "ba"，同样得到 dp["bda"] = 3。

处理 bdca：删下标 $0$ 得 "dca" 未命中；删下标 $1$ 得 "bca"，查到 $3$，best 更新为 $4$；删下标 $2$ 得 "bda"，同样查到 $3$，best 仍为 $4$；删下标 $3$ 得 "bdc" 未命中。写入 dp["bdca"] = 4，答案更新为 $4$。

最终返回 $4$，对应的链是 a → ba → bca → bdca，与题目给出的结果一致。

代码实现

class Solution {
    // 一个单词的前驱只能通过删除一个字符得到，枚举删除位置即可覆盖所有候选前驱。
    public int longestStrChain(String[] words) {
        java.util.Arrays.sort(words, (a, b) -> a.length() - b.length());

        java.util.Map<String, Integer> dp = new java.util.HashMap<>();
        int answer = 0;

        for (String word : words) {
            int best = 1;
            for (int i = 0; i < word.length(); i++) {
                String pre = word.substring(0, i) + word.substring(i + 1);
                best = Math.max(best, dp.getOrDefault(pre, 0) + 1);
            }

            dp.put(word, best);
            answer = Math.max(answer, best);
        }

        return answer;
    }
}

func longestStrChain(words []string) int {
    // 一个单词的前驱只能通过删除一个字符得到，枚举删除位置即可覆盖所有候选前驱。
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })

    dp := make(map[string]int)
    answer := 0

    for _, word := range words {
        best := 1
        for i := 0; i < len(word); i++ {
            pre := word[:i] + word[i+1:]
            if dp[pre]+1 > best {
                best = dp[pre] + 1
            }
        }

        dp[word] = best
        if best > answer {
            answer = best
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n \log n + n L^2)$，其中 n 是单词个数，L 是单词最大长度。排序按长度比较是常数代价，占 $O(n \log n)$；主循环对每个单词枚举 $L$ 个删除位置，每次拼接候选串要复制 $O(L)$ 个字符、哈希查表又要再扫一遍这 $O(L)$ 个字符，所以内层是 $O(L^2)$。代入 $n \le 1000$、$L \le 16$ 约为 $2.6 \times 10^5$ 次字符操作，非常宽裕。

空间复杂度：$O(nL)$，哈希表最坏要为全部 n 个单词各存一份键，键本身占 $O(L)$ 个字符；每轮临时拼出的候选串只占 $O(L)$ 且可被回收，不影响总量。

关键点总结

当「谁能转移到我」这件事可以被直接构造出来时，就不要再去两两枚举配对。本题把 $O(n^2)$ 的连边判断换成 $O(nL)$ 次哈希查询，靠的正是「前身只能是删一个字符的结果」这条强约束。

动态规划不一定要显式建图再拓扑排序。只要能找到一个使依赖单向流动的排序键，遍历顺序本身就是拓扑序。本题的键是单词长度，因为前身必然更短一个字符。

状态的初值要对应「最小的合法解」。这里孤立单词本身就是长度为 $1$ 的链，所以 best 从 $1$ 起步；把它当成「还没有解」而写成 $0$，是这类计数型动态规划最典型的初始化错误。

用「查不到按 $0$ 处理」代替显式的存在性判断，是哈希表型动态规划的常见简化，前提是 $0$ 这个默认值代入转移后不会产生比下界更优的假解。

面试视角：面试官通常会先引导你说出 $O(n^2 L)$ 的朴素解，再问怎么优化。能主动指出「长度差必须为 $1$」并由此想到反向构造前身，比直接写出最终代码更能体现推导能力。

面试视角：常见追问是「如果要输出具体的链而不是长度呢」。要能答出在 dp 里额外记录每个单词的最优前身，最后从答案终点沿指针回溯并反转，这是把计数型动态规划升级为方案型的通用手法。

易错点总结

错误写法：不排序直接按输入顺序做动态规划 → 以 ["ba", "a"] 为例，处理 ba 时 dp["a"] 还没写入，best 只能是 $1$，最终返回 $1$，而正确答案是 $2$。

错误写法：按字典序而不是按长度排序 → 以 ["b", "ab"] 为例，字典序下 "ab" 排在 "b" 之前，处理 ab 时查不到 dp["b"]，返回 $1$，正确答案是 $2$。

错误写法：把 best 初始化为 $0$ → 所有单词的链长整体少 $1$，输入 ["a"] 会返回 $0$，而单个单词本身就是一条长度为 $1$ 的链。

错误写法：删除位置只枚举到 i < word.length() - 1 → 漏掉了删除末位字符的情形，输入 ["b", "ba"] 时 ba 只能构造出 "a"，查不到前身，返回 $1$，正确答案是 $2$。

错误写法：把前身关系判成「短串是长串的连续子串」→ 前身允许插入发生在中间，得到的是子序列而非子串。输入 ["a", "b", "ba", "bca", "bda", "bdca"] 时 "ba" 不是 "bca" 的连续子串，这条边被漏掉，答案退化为 $2$，正确答案是 $4$。

错误写法：用按字符删除的接口（如把某个字母全部替换为空）来构造前身 → 输入含 "aab" 时会一次删掉两个 a 得到 "b"，长度差变成 $2$，构造出的根本不是候选前身，转移全部失真。

错误写法：循环里不维护全局最大值，最后直接返回排序后最后一个单词的 dp 值 → 以 ["a", "ba", "xy"] 为例，排序后 xy 排在末尾且 dp["xy"] = 1，返回 $1$，而经过 a → ba 的链长为 $2$。

错误写法：误以为链上的单词必须在原数组中连续出现，或必须用完全部单词 → 题目只要求链是 words 的一个子集且相邻满足前身关系，加上连续性限制会漏掉绝大多数合法链。

错误写法：担心重复单词把答案算大而先去重再排序 → 相同单词算出的 dp 值完全一致，写回哈希表时互相覆盖也不会产生更长的链，去重这一步是多余的；真正危险的是反过来把「长度相同的两词」也当成可连边。

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	同类链式动态规划的原型，前驱靠比较大小找，还可用贪心加二分优化到 $O(n \log n)$
354. 俄罗斯套娃信封问题	困难	二维偏序，需要对第二维降序排序来规避同宽信封互相嵌套
368. 最大整除子集	中等	转移条件换成整除关系，且要求输出具体子集，需额外记录前驱指针
673. 最长递增子序列的个数	中等	在最长链之外再维护一份方案计数，考察并列最优时的计数合并
面试题 08.13. 堆箱子	困难	三维严格偏序，转移求的是高度之和的最大值而非链的条数
面试题 17.08. 马戏团人塔	中等	数据量逼到 $O(n \log n)$，必须用二分维护而不能写平方级双重循环