Leetcode 1129 Solution

This article provides solution to leetcode question 1129 (longest-string-chain)
Categories:
Tags:
Access this page by simply typing in "lcs 1129" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/longest-string-chain

Solution

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        self.words = set(words)
        self.m = {}

        def dfs(word):
            if word in self.m:
                return self.m[word]

            ans = 1
            for i in range(len(word)):
                new_word = word[:i] + word[i + 1:]
                if new_word not in self.words:
                    continue
                ans = max(ans, dfs(new_word) + 1)
            self.m[word] = ans
            return ans

        ans = 0
        for word in words:
            ans = max(ans, dfs(word))
        return ans