Longest string chain

We will use DFS to find the lognest possible word chain end at word. To calculate dfs(word), we try all predecessors of word word and get the maximum length among them.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        wordSet = set(words)

        @cache
        def dfs(word):
            res = 1
            for i in range(len(word)):
                predecessor = word[:i] + word[i+1:]

                if predecessor in wordSet:
                    res = max(res, dfs(predecessor)+1)

            return res

        return max(dfs(word) for word in words)

Time complexity: O(n^2)
Space complexity: O(n)