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.
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        n = len(words)
        dp = [1] * n
        for i in range(n):
            for j in reversed(list(range(i))):
                if len(words[i]) == len(words[j]):
                    continue
                elif len(words[i]) > len(words[j]) + 1:
                    break
                
                if self.helper(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)
    
    def helper(self, w1, w2):
        # check if w1 is a predecessor of w2
        i = 0
        while i < len(w1) and w1[i] == w2[i]:
            i += 1
        
        while i < len(w1) and w1[i] == w2[i + 1]:
            i += 1
        
        return i == len(w1)

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        n = len(words)
        dp = [1] * n
        for i in range(n):
            for j in reversed(list(range(i))):
                if len(words[i]) == len(words[j]):
                    continue
                elif len(words[i]) > len(words[j]) + 1:
                    break
                
                if self.helper(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)
    
    def helper(self, w1, w2):
        # check if w1 is a predecessor of w2
        i = 0
        while i < len(w1) and w1[i] == w2[i]:
            i += 1
        
        while i < len(w1) and w1[i] == w2[i + 1]:
            i += 1
        
        return i == len(w1)
