Longest String Chain

Given a list of words, each word consists of English lowercase letters.

Let's sayword1is a predecessor ofword2 if and only if we can add exactly one letter anywhere inword1to make it equal toword2. For example, "abc" is a predecessor of"abac".

A_word chain _is a sequence of words[word_1, word_2, ..., word_k] withk >= 1, whereword_1is a predecessor ofword_2,word_2is a predecessor ofword_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list ofwords.

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.

分析

本题顺序可以重组，所以sort,注意可以直接sort(key=len)

每个词只有一个子，所以只要找到子+1就好，dp是dict: word->count

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        n = len(words)
        dp = {w:1 for w in words}
        words.sort(key= len)
        res = 1
        for w in words: 
            for i in range(len(w)):
                nw = w[:i] + w[i+1:]
                if nw in words:
                    dp[w] =dp[nw]+1

        return max(dp[w] for w in words)