LC 1048 [M] Longest String Chain - ALawliet/algorithms GitHub Wiki

{'a': 1, 'b': 1, 'ba': 2, 'bca': 3, 'bda': 3, 'bdca': 4}

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        '''
        time: O(n*l(avg len of word)*l(recursion))
        space: O(n*l*l) for recursion
        '''
        s = set(words) # faster lookup
        memo = {}
        
        def rec(word):
            if word in memo:
                return memo[word]

            if word not in s:
                return 0 # chain does not exist so stop exploring this math

            N = len(word)
            mx = 0
            for i in range(N):
                mx = max(mx, rec(word[:i] + word[i+1:]) + 1) # delete a char
                memo[word] = mx
            return mx
            
        for w in words:
            rec(w)
            
        return max(memo.values())