<p>Given an array of strings <code>words</code> (<strong>without duplicates</strong>), return <em>all the <strong>concatenated words</strong> in the given list of</em> <code>words</code>.</p>

<p>A <strong>concatenated word</strong> is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct)&nbsp;in the given array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;cat&quot;,&quot;cats&quot;,&quot;catsdogcats&quot;,&quot;dog&quot;,&quot;dogcatsdog&quot;,&quot;hippopotamuses&quot;,&quot;rat&quot;,&quot;ratcatdogcat&quot;]
<strong>Output:</strong> [&quot;catsdogcats&quot;,&quot;dogcatsdog&quot;,&quot;ratcatdogcat&quot;]
<strong>Explanation:</strong> &quot;catsdogcats&quot; can be concatenated by &quot;cats&quot;, &quot;dog&quot; and &quot;cats&quot;; 
&quot;dogcatsdog&quot; can be concatenated by &quot;dog&quot;, &quot;cats&quot; and &quot;dog&quot;; 
&quot;ratcatdogcat&quot; can be concatenated by &quot;rat&quot;, &quot;cat&quot;, &quot;dog&quot; and &quot;cat&quot;.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;cat&quot;,&quot;dog&quot;,&quot;catdog&quot;]
<strong>Output:</strong> [&quot;catdog&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= 30</code></li>
	<li><code>words[i]</code> consists of only lowercase English letters.</li>
	<li>All the strings of <code>words</code> are <strong>unique</strong>.</li>
	<li><code>1 &lt;= sum(words[i].length) &lt;= 10<sup>5</sup></code></li>
</ul>

class TrieNode:
    def __init__(self, par = None):
        #words that can be made by adding given letters to this word
        self.children = {}
        #whether the given word exists in words
        self.exists = 0
        #keeps track of parent node. Used to prune the tree when 
        self.par = par

class Trie:
    def __init__(self):
        self.root = TrieNode()

    #adds a word to the trie
    def add(self, word):
        node = self.root
        for c in word:
            if c not in node.children: node.children[c] = TrieNode(par=node)
            node = node.children[c]
        node.exists = 1
    
    #removes the word from the tree and removes the path to it
    #if the current letter is saved in each node, could optimize node removal
    def remove(self, node):
        node.exists = 0
        #Only prune the trie if there are no other words along that path.
        while (not node.exists) and (not node.children):# and node.par:
            par = node.par
            #O(1); 26 keys maximum in children
            for c in node.par.children:
                if node.par.children[c] == node:
                    node.par.children.pop(c)
                    break
            node = par
        return
            
        


    #given a word, returns whether it can be created using words in the array
    #
    def isConcat(self, word):
        #cached dfs using a node in the tree and an index in the word
        @lru_cache(maxsize=None)
        def dfs(i):
            node = self.root
            if i == len(word): return 1
            found = 0
            depth = 0
            while i+depth < len(word) and word[i+depth] in node.children:
                node = node.children[word[i+depth]]
                depth+=1 #depth increases by 1 when node goes to its child
                if node.exists:
                    if depth == len(word):
                        if found: self.remove(node)
                        return found
                    if not found:
                        found |= dfs(i+depth)
            return found
        return dfs(0)


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        trie = Trie()
        [trie.add(word) for word in words]
        words.sort(key=lambda x: len(x))
        return [word for word in words if trie.isConcat(word)]
        
37053