BinarySearch 1027 Longest Prefix Sequence

Problem statement

https://binarysearch.com/problems/Longest-Prefix-Sequence/

Solution

Variation of Leetcode 1048. Longest String Chain, but here we can add only to the end.

Complexity

It is O(m) for time, where m is the total length of words. Space is the same.

Code

class Solution:
    def solve(self, words):
        set_words = set(words)
        
        @lru_cache(None)
        def dp(word):
            if word not in set_words: return 0
            return dp(word[:-1]) + 1
           
        return max(dp(word) for word in words)