"""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: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".
Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
 

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters."""
from typing import List
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words = sorted(words, key=lambda x: len(x))
        dp = [1]*len(words)
        for i in range(len(words)):
            for j in range(i):
                if is_predecessor(words[j], words[i]):
                    dp[i] = max(1+dp[j], dp[i])
        return max(dp)
    
def is_predecessor(one, two):
    if len(two) != len(one) + 1:
        return False
    i = 0
    while one != '':
        if one[i] == two[i]:
            one = one[1:]
            two = two[1:]
        else:
            return two[1:] == one
    return True