Skip to main content

1048. Longest String Chain

Python​

Top-Down DP​

from functools import cache


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

        @cache
        def dp(word: str):
            max_length = 1
            for i in range(len(word)):
                new_word = word[:i] + word[i+1:]

                if new_word in words:
                    max_length = max(max_length, 1+dp(new_word))

            return max_length


        answer = 0
        for word in words:
            answer = max(answer, dp(word))

        return answer

Bottom-Up DP​

from collections import defaultdict


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

        words.sort(key=lambda word: len(word))

        answer = 0

        for word in words:
            current_length = 1
            for i in range(len(word)):
                new_word = word[:i] + word[i+1:]
                pre_length = dp.get(new_word, 0)
                current_length = max(current_length, pre_length+1)

            dp[word] = current_length
            answer = max(answer, current_length)

        return answer