<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 Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        return self._sol2(words)

    def _sol2(self, words: List[str]) -> List[str]:
        words_by_size = collections.defaultdict(set)
        for w in words:
            words_by_size[len(w)].add(w)
        all_sizes = list(words_by_size.keys())
        all_sizes.sort()
        @cache
        def is_concatenated(w: str) -> bool:
            for other_size in all_sizes:
                if other_size >= len(w):
                    break
                if w[:other_size] in words_by_size[other_size]:
                    remainder = w[other_size:]
                    if remainder in words_by_size[len(remainder)] or is_concatenated(remainder):
                        return True
            return False
        res = []
        for i in range(1, len(all_sizes)):
            for w in words_by_size[all_sizes[i]]:
                if is_concatenated(w):
                    res.append(w)
        return res


























    # Damn time limit exceed on test case 4 of 43.
    # Pfft just some memoization got us to 33.3% 445 ms, 5.4% 43.9 mb.
    # There's one main taller curve around 300 ms, a smaller one around us, and a smaller one yet up at 700 ms.
    #   I grabbed some from the peak of the smaller curve, it's basically mine with simpler code (in some ways fewer optimizations)
    #   but one nice change is that when splitting the string it only recurses on the latter half and just does a straight word search
    #   on the first part.
    # 95.2% 269 ms! 59.1% 28.6 mb. Same basic approach, just some nice optimizations and cleanup.
    def _sol1(self, words: List[str]) -> List[str]:
        words_by_size = {}
        for word in words:
            if len(word) not in words_by_size:
                words_by_size[len(word)] = {word}
            else:
                words_by_size[len(word)].add(word)
        min_size = min(words_by_size.keys())
        smallest_concatenated_size = 2 * min_size
        results = []
        memo = {}
        def helper(s: str) -> bool:
            if s in memo:
                return memo[s]
            result = False
            for i in range(min_size, len(s) - min_size + 1):
                prefix = s[:i]
                suffix = s[i:]
                if len(prefix) in words_by_size and prefix in words_by_size[len(prefix)]:
                    if len(suffix) in words_by_size and suffix in words_by_size[len(suffix)]:
                        result = True
                        break
                    if len(suffix) >= smallest_concatenated_size and helper(suffix):
                        result = True
                        break
            memo[s] = result 
            return result
        for word_len, word_set in words_by_size.items():
            if word_len < smallest_concatenated_size:
                continue
            for word in word_set:
                if helper(word):
                    results.append(word)
        return results
            
            
26728