LeetCode 1048. 最长字符串链

约 5 分钟
文章信息 7 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 微软
标签
数组 字符串 哈希表 动态规划 排序 双指针

题目描述

✅ 1048. 最长字符串链

image-20260928225529652

image-20260928225529653

题意分析

从给定单词集合中选择若干单词组成一条链，相邻两词必须满足：在前一个词中插入恰好一个字母、不改变其余字符顺序，就能得到后一个词。链长统计单词数量，单个词本身也构成长为一的链。

单词不必按输入顺序选取，但每个中间词都必须实际出现在输入中。每一步长度增加一，不能跳过长度，也不能用换序或替换一个字符代替插入。

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

核心思路

[!blue]

当前词的合法前身一定比它短一个字符。先按长度升序处理，就能保证计算某个词时，它可能依赖的前身已经计算完；同长度的词之间没有转移关系，所以它们内部如何排序都不影响结果。

定义 dp[word] 为以当前词结尾的最长链长。与其在较短单词中逐个寻找能插入变成当前词的对象，不如反过来：枚举删除当前词中的一个位置，保持剩余字符顺序，就得到它的一个候选前身。

若这个前身在哈希表中，接在它的最长链后就得到候选长度 dp[pre] + 1。枚举所有删除位置能覆盖所有可能插入关系，取最大值即可；若没有任何前身出现，当前词自己开一条链，长度为一。

任意一条以当前词结尾、长度超过一的合法链，其倒数第二个词必定是某个删除位置产生的前身，因此上述转移不会漏掉更长链。删除不同位置可能得到相同前身，但这里只取最大值，不会因重复候选多计算链长。

每个单词处理完后写回自己的最优链长，并更新全局答案。最长链不一定以最长单词结尾，所以不能只返回排序后最后一词的状态。代码会改变输入单词数组的排列顺序，但不会修改单词内容。

解题步骤

  1. 将单词按长度升序排序，创建保存各词最长结尾链的哈希表。
  2. 对当前单词，初始化 best = 1，表示仅使用它自己。
  3. 枚举每个字符位置，只删除该位置一次，得到候选前身。
  4. 用前身已有链长加一更新 best；前身未出现时，默认零不会把候选提高到一以上。
  5. 保存当前词状态并更新全局最大值，最后返回全局答案。

代码实现

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

import "sort"

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
}

复杂度分析

设单词数为 $n$，最大词长为 $L$。

  • 时间复杂度：期望为 $O(n\log(n+1)+nL^2)$。排序比较长度，随后每词最多构造 $L$ 个前身；每个候选的拼接和哈希需要 $O(L)$。
  • 辅助空间复杂度：$O(n+L)$。哈希表键引用输入单词，保存 $O(n)$ 个链长状态；临时候选字符串占 $O(L)$，排序辅助空间也被该上界覆盖。

关键点总结

[!green]

  • 按长度处理就满足前身先于后继的依赖顺序。
  • 枚举删除一个位置，等价于枚举所有恰好插入一个字符的前身。
  • 状态属于以某词结尾的链，全局答案需要在所有终点中取最大值。

易错点总结

[!yellow]

  • 字典序不能代替长度顺序，否则后继可能先于前身计算。
  • 删除一个字符值的所有出现位置会缩短多位；必须只删除当前枚举的一个下标。
  • 前身必须存在于输入词集合中，不能把任意删出的字符串当作已有链。
  • 链长按单词数计数，不是字符数，也不是转移次数。
  • 只返回最后一个词的状态会遗漏结束于其他单词的更长链。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 同样在偏序关系中求最长链，本题前驱条件是恰少一个字符而非数值更小。
161. 相隔为 1 的编辑距离 中等 长度相差1时可检查一次插入关系，原题还允许替换，本题必须额外满足长度差。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/99571062
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！