leetcode-1048 最长字符串链

leetcode-1048 最长字符串链

参考:doudoucao

题目描述:

给出一个单词列表,其中每个单词都由小写英文字母组成。如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1 是 word2 的前身。例如,"abc" 是 "abac" 的前身。词链是单词 [word_1, word_2, ..., word_k] 组成的序列,k >= 1,其中 word_1 是 word_2 的前身,word_2 是 word_3 的前身,依此类推。从给定单词列表 words 中选择单词组成词链,返回词链的最长可能长度
注:在评论区看到这个做法,真的是太强了

from collections import defaultdict
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        res = defaultdict(int)
        for word in words:
            res[word]=max(res[word[:i]+word[i+1:]] for i in range(len(word))) + 1
        return max(res.values())
上一篇:SDNU 1048.石子合并2(区间合并)


下一篇:1048 数字加密