1048. Longest String Chain - cocoder39/coco39_LC GitHub Wiki

1048. Longest String Chain

tip: instead of inserting a char into current word to get next word, we remove letter from current word to get previous word

time complexity: O (N * lg N) for sorting. O(N * L * L) in for-loop so

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        dp = {}
        res = 1
        for word in sorted(words, key = len):
            dp[word] = 1
            for i in range(len(word)):
                pre = word[:i] + word[i+1:]
                if pre in dp:
                    dp[word] = max(dp[word], dp[pre] + 1)
                    res = max(res, dp[word])
        return res