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

def delta_len(wi, wj):
  for i in range(len(wi)):
    if wj.startswith(wi[i:]):
      shared_len = len(wi) - i
      return len(wj) - shared_len
  return len(wj)


class Solution:
  def shortestSuperstring(self, words: List[str]) -> str:
    n = len(words)
    word_to_dists = [[0]*n for _ in range(n)]
    for i, wi in enumerate(words):
      for j, wj in enumerate(words):
        if i == j: continue
        word_to_dists[i][j] = delta_len(wi, wj)

    # Value of dp: (min distance, next word id to choose given this state to reach this min distance).
    dp = [[(-1, -1) for _ in range(n)] for _ in range(1 << n)]

    done_mask = (1 << n) - 1

    def helper(mask, cur_w):
      # print("mask: ", bin(mask), ", done_mask: ", bin(done_mask))
      if mask == done_mask:
        return 0, -1

      if dp[mask][cur_w] != (-1, -1):
        return dp[mask][cur_w]

      # Iterate over all the unvisited cities
      min_dist = math.inf
      min_next = None
      for next_w, dist in enumerate(word_to_dists[cur_w]):
        if (mask & (1 << next_w)) or next_w == cur_w:
          continue
        # print("mask: ", bin(mask), ", cur_city: ", cur_city, ", next_w: ", next_w, ", bit: ", bin(1 << next_w), ", dist: ", dist)
        # Otherwise, set the bit for the city, indicating they've been visited.
        next_dist, _ = helper(mask | (1 << next_w), next_w)
        cur_dist = dist + next_dist
        if min_dist > cur_dist:
          min_next = next_w
          min_dist = cur_dist
      # print("\n--\nmask: ", bin(mask), ", cur_city: ", cur_city, ", min_next_city: ", min_next_city)
      dp[mask][cur_w] = (min_dist, min_next)
      return dp[mask][cur_w]

    min_path_cost = math.inf
    min_start = None
    for start_w in range(n):
      start_mask = 1 << start_w
      next_dist, _ = helper(start_mask, start_w)
      cur_dist = len(words[start_w]) + next_dist
      if cur_dist < min_path_cost:
        min_path_cost = cur_dist
        min_start = start_w

    ordered_parts = [words[min_start]]
    cur_mask = 1 << min_start
    while True:
      _, next_w = dp[cur_mask][min_start]
      if next_w < 0:
        break
      dist = word_to_dists[min_start][next_w]
      # print("cur_w: ", words[min_start], "next_w: ", words[next_w], ", dist: ", dist)
      ordered_parts.append(words[next_w][-dist:])
      min_start = next_w
      cur_mask |= 1 << min_start
    return "".join(ordered_parts)
26700