<p>Given an array of strings <code>words</code>, return <em>the smallest string that contains each string in</em> <code>words</code> <em>as a substring</em>. If there are multiple valid strings of the smallest length, return <strong>any of them</strong>.</p>

<p>You may assume that no string in <code>words</code> is a substring of another string in <code>words</code>.</p>

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

<pre>
<strong>Input:</strong> words = [&quot;alex&quot;,&quot;loves&quot;,&quot;leetcode&quot;]
<strong>Output:</strong> &quot;alexlovesleetcode&quot;
<strong>Explanation:</strong> All permutations of &quot;alex&quot;,&quot;loves&quot;,&quot;leetcode&quot; would also be accepted.
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;catg&quot;,&quot;ctaagt&quot;,&quot;gcta&quot;,&quot;ttca&quot;,&quot;atgcatc&quot;]
<strong>Output:</strong> &quot;gctaagttcatgcatc&quot;
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 12</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 20</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
	<li>All the strings of <code>words</code> are <strong>unique</strong>.</li>
</ul>

class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:

        def getOverlappingWords(target, words, visited):
            for word in words:
                if target not in visited and target == word[0:len(target)]:
                    yield word
        
        def combine(s1, prev_word, s2, g):
            if prev_word in g:
                if s2 in g[prev_word]:
                    return s1 + s2[len(prev_word) - g[prev_word][s2]:]

            if s2 in s1:
                return s1
            
            return s1 + s2

        def dp(s, prev_word, words_set, g, mem):
            if (prev_word, tuple(words_set)) in mem:
                return mem[(prev_word, tuple(words_set))]

            if not words_set:
                return ''

            remaining_words = set(words_set)
            res = s + ''.join(words_set)
            for word in words_set:
                remaining_words.remove(word)
                tmp = combine(s, prev_word, word, g) + dp(combine(s, prev_word, word, g), word, remaining_words, g, mem)
                if len(tmp) < len(res):
                    res = tmp
                    
                remaining_words.add(word)
            mem[(prev_word, tuple(words_set))] = res[len(s):]
            return res[len(s):]

        g = {}
        for word in words:
            g.setdefault(word, {})
            visited = set()
            visited.add(word)
            for i in range(1, len(word)+1):
                overlap = len(word) - i
                for overlapping_word in getOverlappingWords(word[i:], words, visited):
                    g[word].setdefault(overlapping_word, len(word) - overlap)
                    visited.add(overlapping_word)

        mem = {}
        return dp('', '', set(words), g, mem)
26200