BinarySearch 0581 Word Concatenation

Problem statement

https://binarysearch.com/problems/Word-Concatenation/

Solution

Equal to Leetcode 0472. Concatenated Words.

Complexity

Time is O(n*m^3), where n = len(words), m = max(len(w)). Space is O(mn).

Code

class Solution:
    def solve(self, words):
        d = set(words)
        
        @lru_cache(None)
        def dfs(word):
            for i in range(1, len(word)):
                if word[:i] in d and (word[i:] in d or dfs(word[i:])):
                    return True
            return False
        
        return len([word for word in words if dfs(word)])