<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>

from functools import lru_cache
from itertools import permutations

class Solution:
    def shortestSuperstring(self, words):
        words.insert(0, '~')  # start from nowhere

        # build cost matrix
        L, prefix = len(words), {w: {w[:i + 1] for i in range(len(w))} for w in words}
        cost = [[0] * L for _ in range(L)]

        for l, r in permutations(range(L), 2):
            lw, rw = words[l], words[r]

            cost[l][r] = len(rw)  # default
            for i in range(len(lw)):  # greadily find shorter
                if lw[i] == rw[0] and lw[i:] in prefix[rw]:
                    cost[l][r] = len(rw) - (len(lw) - i)
                    break

        # solve traveling salesman problem
        @lru_cache(None)
        def tsp(used, i):
            nonlocal L
            assert (i != 0)
            if used & (used - 1) == 0: return (cost[0][i], [i])
            used -= (1 << i)

            min_tsp, min_path = float('inf'), []
            for j in range(1, L):
                if j == i: continue
                if (used & (1 << j)) == 0: continue

                candidate, path = tsp(used, j)
                candidate += cost[j][i]

                if candidate <= min_tsp:
                    min_tsp, min_path = candidate, path

            return (min_tsp, min_path + [i])

        used = 2**L - 1 - 1  # index 0 not consider, when L is 3, mask should be 1110
        _, path = min(tsp(used, i) for i in range(1, L))

        # building answer from DP result
        path, shortest_superstring = [0] + path, ''

        for i in range(1, len(path)):
            l, r = path[i - 1], path[i]
            if cost[l][r] == 0: continue
            shortest_superstring += words[r][-cost[l][r]:]

        return shortest_superstring
33900