human
Solve in Python:
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.
 Can you provide a the Python program you requested?
assistant
#Here is the Python program you requested.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        # sort by decreasing length
        # define vector L of length len(words) such that it's the longest 
        # word chain starting from that word
        # then recuriosn is L_k = 1 if it is not predecessor of any 1 longer words
        # otherwise it is 1 + max L_j for j such that k is predecessor of them
        
        lengths = [len(word) for word in words]
        wordsSorted = [x for _,x in sorted(zip(lengths,words),reverse = True)]
        
        print(wordsSorted)
        L = [1]*len(wordsSorted)
        maxLength = max(lengths)
        for k in range(0, len(L)):
            lenWord = len(wordsSorted[k])
            for l in range(k):
                if len(wordsSorted[l]) == lenWord+1 and (set(wordsSorted[l]) & set(wordsSorted[k])) == set(wordsSorted[k]):
                    L[k] = max(L[k], 1 + L[l])
        return(max(L))