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())

leetcode-1048 最长字符串链

原文：https://www.cnblogs.com/curtisxiao/p/11319349.html