[Python3] hash
\n\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        seen = set(words)\n        \n        @cache\n       
\n```\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        seen = set(words)\n        \n        @cache\n        def fn(word):\n            """Return True if input is a concatenated word."""\n            for i in range(1, len(word)): \n                prefix = word[:i]\n                suffix = word[i:]\n                if prefix in seen and (suffix in seen or fn(suffix)): return True \n            return False \n        \n        ans = []\n        for word in words: \n            if fn(word): ans.append(word)\n        return ans \n```\n\n```\nclass Trie: \n    \n    def __init__(self): \n        self.root = {}\n        \n    def insert(self, word): \n        node = self.root\n        for ch in reversed(word): \n            node = node.setdefault(ch, {})\n        node["#"] = True\n        \n    def search(self, word): \n        """Return True if input is a concatenated word."""\n        dp = [True] + [False] * len(word)\n        for i in range(len(word)): \n            node = self.root\n            for j in reversed(range(i+1)): \n                if word[j] not in node: break \n                node = node[word[j]]\n                if dp[j] and node.get("#"):\n                    dp[i+1] = True \n                    break \n        return dp[-1]\n\n\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        ans = []\n        trie = Trie()\n        for word in sorted(words, key=len): \n            if word: \n                if trie.search(word): ans.append(word)\n                trie.insert(word)\n        return ans\n```
['Python3']