1048. Longest String Chain (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        # dp solution
        h = {}
        result = 1
        words.sort(key = len)
        for word in words:
            if word not in h:
                cur = 1
                for i in range(len(word)):
                    cur = max(cur, h.get(word[ : i] + word[i + 1 : ], 0) + 1)
                h[word] = cur
                result = max(cur, result)
        return result
        
        # my dumb solution
        def isPred(a, b):
            if len(a) != len(b) - 1:
                return False
            i = j = 0
            flag = 0
            while i < len(a):
                if a[i] != b[j]:
                    if flag:
                        return False
                    else:
                        j += 1
                        flag = 1
                else:
                    i += 1
                    j += 1
            return True
        words.sort(key = len)
        result = 1
        h = {}
        for word1 in words:
            if word1 not in h:
                h[word1] = 1
            for word2 in h:
                if isPred(word2, word1):
                    h[word1] = max(h[word1], h[word2] + 1)
                    result = max(result, h[word1])
        return result