'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    # dp version
    def findAllConcatenatedWordsInADict1(self, words: List[str]) -> List[str]:
        memo = {}
        words = set(words) # must have this line! If not, TLE
        def dfs(word):
            if word in memo:
                return memo[word]
            memo[word] = False
            for i in range(1, len(word)):
                prefix = word[:i]
                suffix = word[i:]
                if prefix in words and suffix in words:
                    memo[word] = True
                    break # terminate the for loop
                if prefix in words and dfs(suffix):
                    memo[word] = True
                    break
                # if suffix and dfs(prefix):
                #     memo[word] = True
        
        return [word for word in words if dfs(word)]
        
    
    
    # TLE
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words = set(words) # must have this line!
        def dfs(word):
            for i in range(1, len(word)):
                prefix = word[:i]
                suffix = word[i:]
                
                if prefix in words and suffix in words:
                    return True
                if prefix in words and dfs(suffix):
                    return True
                # the following two lines can be commented out
                if suffix in words and dfs(prefix):
                    return True
            return False
        
        res = []
        for word in words:
            if dfs(word):
                res.append(word)
        return res
    
sol = Solution()
sol.findAllConcatenatedWordsInADict1(["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"])    
    
