What is the main pattern used in Find the Shortest Superstring?

The problem is solved using state transition dynamic programming with bitmasking to track subsets of words efficiently.

Can the words in the input array be substrings of each other?

No, the problem guarantees that no word is a substring of another, simplifying overlap calculations.

Why is a brute-force permutation approach impractical?

Because the number of permutations grows factorially with the number of words, leading to infeasible computation for N > 10.

How are overlaps computed between two words?

For each pair, calculate the longest suffix of the first matching a prefix of the second, which determines the maximal overlap length.

Does GhostInterview provide step-by-step reconstruction guidance?

Yes, it walks through the backtracking of the DP table to assemble the shortest superstring correctly.

#943

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最短超级串

给定一个字符串数组 words ，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中任意一个即可。我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。示例 1：输入： words = ["alex","lov…

数组字符串动态规划位运算位掩码

题目描述

给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。

我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。

示例 1：

输入：words = ["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。

示例 2：

输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"

提示：

1 <= words.length <= 12
1 <= words[i].length <= 20
words[i] 由小写英文字母组成
words 中的所有字符串 互不相同

lightbulb

解题思路

方法一：状态压缩 + 动态规划

由于题目中字符串数组 words 的长度不超过 12，因此可以使用状态压缩的方法来表示字符串数组中的每个字符串是否被选中。

定义 $dp[i][j]$ 表示字符串当前选中状态为 $i$ ，且最后一个选中的字符串为 $s[j]$ 时，字符串重叠部分的最大长度。其中 $i$ 的二进制表示中的第 $j$ 位为 $1$ 表示字符串 $s[j]$ 被选中，为 $0$ 表示字符串 $s[j]$ 未被选中。重叠部分达到最大时，最终得到的字符串最短。我们只要求出重叠部分的最大值以及对应的字符串 $s[j]$ ，记录每一步状态转移，就能够逆推出最终的字符串。

字符串两两之间的重叠部分长度可以预处理出来，存储在二维数组 $g$ 中，其中 $g[i][j]$ 表示字符串 $s[i]$ 和字符串 $s[j]$ 之间的重叠部分长度。

动态规划的状态转移方程如下：

dp[i][j] = \max_{k \in \{0, 1, \cdots, n - 1\}} \{dp[i - 2^j][k] + g[k][j]\}

时间复杂度 $O(2^n \times n^2)$ ，空间复杂度 $O(2^n \times n)$ 。其中 $n$ 为字符串数组 words 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:
        n = len(words)
        g = [[0] * n for _ in range(n)]
        for i, a in enumerate(words):
            for j, b in enumerate(words):
                if i != j:
                    for k in range(min(len(a), len(b)), 0, -1):
                        if a[-k:] == b[:k]:
                            g[i][j] = k
                            break
        dp = [[0] * n for _ in range(1 << n)]
        p = [[-1] * n for _ in range(1 << n)]
        for i in range(1 << n):
            for j in range(n):
                if (i >> j) & 1:
                    pi = i ^ (1 << j)
                    for k in range(n):
                        if (pi >> k) & 1:
                            v = dp[pi][k] + g[k][j]
                            if v > dp[i][j]:
                                dp[i][j] = v
                                p[i][j] = k
        j = 0
        for i in range(n):
            if dp[-1][i] > dp[-1][j]:
                j = i
        arr = [j]
        i = (1 << n) - 1
        while p[i][j] != -1:
            i, j = i ^ (1 << j), p[i][j]
            arr.append(j)
        arr = arr[::-1]
        vis = set(arr)
        arr.extend([j for j in range(n) if j not in vis])
        ans = [words[arr[0]]] + [words[j][g[i][j] :] for i, j in pairwise(arr)]
        return ''.join(ans)

speed

复杂度分析

指标	值
时间	complexity is O(N^2 * 2^N + N^2 * W) due to computing overlaps and DP transitions, where N is the number of words and W is the average word length. Space complexity is O(N * 2^N + N^2) to store DP states and overlaps.
空间	O(N (2^N + W))

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion of bitmask DP and its exponential subset growth pattern.
question_mark
Look for correct calculation of word overlaps and handling edge cases in reconstruction.
question_mark
Watch for clarity in state transition definition and why each DP entry correctly represents a partial solution.

warning

常见陷阱

外企场景

error
Ignoring the fact that overlaps are directional and dp[i][mask] must track the ending word.
error
Attempting brute-force permutation generation which is infeasible for N > 10.
error
Forgetting to reconstruct the string correctly after DP, leading to invalid superstrings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize superstring for a subset of words where some words may repeat.
arrow_right_alt
Find a superstring using weighted overlaps for prioritizing certain word concatenations.
arrow_right_alt
Compute the shortest superstring but allow some words to be omitted based on constraints.

help

常见问题

外企场景

继续练习

#691 贴纸拼词 #1255 得分最高的单词集合 #996 平方数组的数目