LeetCode 1048. 最长字符串链

Categories:

题目描述
思路分析
1. 解法一：排序 + DP（推荐）
相似题目

题目描述

✅ 1048. 最长字符串链

思路分析

解法一：排序 + DP（推荐）

核心思路：

按长度升序排序，保证转移只从更短单词到更长单词。

dp[word] 表示以该单词结尾的最长链长度。

枚举删除一个字符得到前驱，更新 dp[word]。

复杂度分析：

时间复杂度：O(L * m)，其中 L 为单词数量，m 为单词平均长度。

空间复杂度：O(L)，用于哈希表存储。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> dp = new HashMap<>();
        int res = 0;

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

        return res;
    }
}

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)
	res := 0

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

	return res
}

相似题目

题目	难度	考察点
472. 连接词	困难	单词拆分
720. 词典中最长的单词	简单	字符串
139. 单词拆分	中等	动态规划
140. 单词拆分 II	困难	回溯
300. 最长递增子序列	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/99571062