Hard

Find the Shortest Superstring

LAB

Return the shortest string that contains every word as a substring. If ties exist, return the lexicographically smallest one.

EXAMPLES

Example 1

Input
{
  "words": [
    "alex",
    "loves",
    "leetcode"
  ]
}

Output
"alexlovesleetcode"

FUNCTION SHAPE

words: stringArray→string

SOLUTION NOTE

TSP-like. Precompute overlaps. DP finds optimal ordering to minimize total non-overlapping length.

Reveal reference solution +

pythonREFERENCE

def shortestSuperstring(self, words: List[str]) -> str:
    n = len(words)

    # Precompute overlap[i][j] = max overlap when words[i] followed by words[j]
    overlap = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                for k in range(min(len(words[i]), len(words[j])), 0, -1):
                    if words[i][-k:] == words[j][:k]:
                        overlap[i][j] = k
                        break

    @cache
    def dp(mask, last):
        if mask == (1 << n) - 1:
            return ""
        best = None
        for i in range(n):
            if not (mask & (1 << i)):
                suffix = words[i][overlap[last][i]:] if last != -1 else words[i]
                candidate = suffix + dp(mask | (1 << i), i)
                if best is None or len(candidate) < len(best):
                    best = candidate
        return best

    return dp(0, -1)

TimeO(n² × 2^n)

SpaceO(n × 2^n)

Open on LeetCode ↗