Longest String Chain(Python - Bottom Up)

longest_string_chain.python

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)  # sort words by its length
        ans = 0
        cnt = defaultdict(int)
        for word in words:
            cnt[word] = 1
            for i in range(len(word)):
                predecessor = word[:i] + word[i+1:]
                if predecessor in cnt and cnt[word] < cnt[predecessor] + 1:
                    cnt[word] = cnt[predecessor] + 1
            ans = max(ans, cnt[word])
        return ans