DFS with memo

472. Concatenated Words

Without memo will get TLE. With memo gets AC.

from functools import lru_cache
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words_set = set(words)
        
        @lru_cache(None)
        def dfs(word):
            this_res = -float('inf')
            if not word:return 0
            w = ""
            for i, c in enumerate(word):
                w += c
                if w in words_set:
                    this_res = max(this_res, 1+dfs(word[i+1:]))
            return this_res
            
        return [word for word in words if dfs(word)>1]

Another way

from functools import lru_cache
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        d = set(words)
        @lru_cache(None)
        def dfs(word):
            for i in range(1, len(word)):
                prefix, suffix = word[:i], word[i:]
                good_pre , good_suf = prefix in d, suffix in d
                if  good_pre and good_suf: return True
                if good_pre and dfs(suffix): return True
                if good_suf and dfs(prefix): return True
            
            return False
        
        return [word for word in words if dfs(word)]