leetcode|LeetCode 1048. Longest String Chain leetcode|python3

Given a list of words, each word consists of English lowercase letters.
Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Input: ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: one of the longest word chain is "a","ba","bda","bdca".

Note:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.

-------------------------------------------------------------------------------------------
非常好的一道题目，直接想到的是DFS，假设存在n个单词，每个单词平均长度是l，那么没两个单词判断是不是前驱需要的复杂度是O(l)，总体加上记忆化搜索的复杂度是O(n^2*l)，当然n^2可以优化，但是优化到多少不好说，而且优化剪枝写起来非常烦躁，得根据长度进行预处理，又浪费了不少空间。
另外一种思路是从长度入手，每个词可能的前驱规模是O(l)，如果某个前驱的个数知道，那么可以直接递推求最大值就好。求某个词所有前驱的复杂度是O(l^2)，所以整体的复杂度是O(n*l^2)，当然需要预先排序，在n>>l的情况下，显然这种思路更好，以下是代码：

class Solution: def longestStrChain(self, words): words.sort(key=lambda x:len(x)) dp = {} for word in words: dp[word] = max(dp[word[:i]+word[i+1:]]+1 if word[:i]+word[i+1:] in dp else 0 for i in range(len(word))) return max(dp.values()) s = Solution() print(s.longestStrChain(["a","b","ba","bca","bda","bdca"]))

【leetcode|LeetCode 1048. Longest String Chain】