leetcode1048 Longest String Chain

英文原题

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

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

分析

    比较容易想到用动态规划来做这个题目，先把单词按照长度排序，从前往后记录每个单词以这个单词结尾时最长的单词串多长，后面再碰到的单词则从前面找它的predecessor。     这题有一个小技巧，我们可以用字典来保存，键是单词，值是这个单词为结尾最长的串的长度，这样比用数组保存可以节约很多时间。

python 代码

这个是用list保存的方法：

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        n = len(words)
        dp = [1] * n
        
        words.sort(key = len)
        minlen = len(words[0])
        
        for i in range(n):
            if len(words[i]) == minlen:
                dp[i] = 1
            else:
                for j in range(i):
                    if self.isPredecessor(words[j], words[i]):
                        dp[i] = max(dp[i], dp[j]+1)
        
        return max(dp)
    
    def isPredecessor(self, word1, word2):
        if len(word2) - len(word1) != 1:
            return False
        for i in range(len(word2)):
            if word1 == word2[:i] + word2[i+1:]:
                return True
        return False

还需要判断是不是predecessor，时间复杂度就上来了。

这个是用字典：

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        n = len(words)
        dp = collections.defaultdict(int)
        
        words.sort(key = len)
        
        for word in words:
            dp[word] = max(dp.get(word[:i]+word[i+1:], 0)+1 for i in range(len(word)))
        
        return max(dp.values())