Skip to content

943. Find the Shortest Superstring

Difficulty Topics

Description

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

 

Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

 

Constraints:

  • 1 <= words.length <= 12
  • 1 <= words[i].length <= 20
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Solution

find-the-shortest-superstring.py
class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:

        def distance(s1, s2):
            for i in range(1, len(s1)):
                if s2.startswith(s1[i:]):
                    return len(s1) - i + 1

            return 1

        n = len(words)
        weights = [[0] * n for _ in range(n)]
        dp = [[0] * n for _ in range(1 << n)]
        queue = deque([(0, i, 1 << i, [i]) for i in range(n)])
        full_mask = (1 << n) - 1
        maxWeight, maxPath = -1, []

        for i in range(n):
            for j in range(i, n):
                weights[i][j] = distance(words[i], words[j])
                weights[j][i] = distance(words[j], words[i])

        while queue:
            w, node, mask, path = queue.popleft()

            if dp[mask][node] != w:
                continue

            if mask == full_mask and w > maxWeight:
                maxWeight = w
                maxPath = path
                continue

            for nei in range(n):
                if mask & (1 << nei) > 0: continue

                new_mask = mask | (1 << nei)
                old = dp[new_mask][nei]
                new = dp[mask][node] + weights[node][nei]

                if new > old:
                    dp[new_mask][nei] = new
                    queue.append((new, nei, new_mask, path + [nei]))

        res = words[maxPath[0]]

        for i in range(1, n):
            prev, curr = maxPath[i - 1], maxPath[i]
            overlap = weights[prev][curr] - 1
            res += words[curr][overlap:]

        return res