LC 0472 [H] Concatenated Words - ALawliet/algorithms GitHub Wiki

similar to Word Break DP problems: https://leetcode.com/problems/concatenated-words/discuss/836924/Python-Template-Word-Break-I-Word-Break-II-Concatenated-Words

or simple memoized DFS

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordDict = set(words)
        
        @cache
        def canForm(word):
            for i in range(1, len(word)):
                prefix = word[:i] ; suffix = word[i:]
                if prefix in wordDict:
                    if suffix in wordDict or canForm(suffix):
                        return True
            return False
        
        return [word for word in words if canForm(word)]

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordDict = set(words)
        cache = {}
        return [word for word in words if self._canForm(word, wordDict, cache)]

    def _canForm(self, word, wordDict, cache):
        if word in cache:
            return cache[word]
        for index in range(1, len(word)):
            prefix = word[:index]
            suffix = word[index:]
            if prefix in wordDict:
                if suffix in wordDict or self._canForm(suffix, wordDict, cache):
                    cache[word] = True
                    return True
            cache[word] = False
        return False

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        d = set(words)
        
        def dfs(word):
            for i in range(1, len(word)):
                prefix = word[:i]
                suffix = word[i:]
                
                if prefix in d and suffix in d:
                    return True
                if prefix in d and dfs(suffix):
                    return True
                if suffix in d and dfs(prefix):
                    return True
            
            return False
        
        res = []
        for word in words:
            if dfs(word):
                res.append(word)
        
        return res

input = ['cat','cats','dog','catsdog']
print(Solution().findAllConcatenatedWords(input))
# ['catsdog']

O(n*m^2) DP