题目描述

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

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

样例

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

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

注意

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

算法

(状态压缩动态规划) $O(2^n n^2)$

1. 假设 $mask$ 表示一个集合，设 $f(mask, i)$ 表示已经满足了 $mask$ 中的字符串，且结尾的字符串是 words 中的第 $i$ 个时的最短长度。
2. 转移时，每次枚举一个在 $mask$ 中的字符串 $i$ 当做结尾 ，然后再枚举一个不在 $mask$ 中的字符串 $j$，预处理 $i$ 的后缀和 $j$ 的前缀重叠的个数。匹配时注意，$j$ 的末尾位置不能小于 $i$ 的末尾。
3. 初始时，$mask$ 中只加入一个字符串，长度为当前字符串的长度。
4. 答案为以 $mask$ 为全集，以$i$ 为结尾的字符串中的最小值。
5. $mask$ 可以用一个二进制数字表示，二进制位为 0 则字符串不存在，为 1 则字符串存在。
6. 最后生成答案是只需要按照动态规划的最优值往回找，动态规划的过程中用 $g(mask, i)$ 记录本次转移的前驱字符串下标。

时间复杂度

• 状态数为 $O(2^n n)$，转移需要 $O(n)$ 的时间，故总时间复杂度为 $O(2^n n^2)$。

C++ 代码

const int N = 12;

class Solution {
private:
    int f[1 << N][N], g[1 << N][N];
    int w[N][N];

    int calc(const string &a, const string &b) {
        const int la = a.size(), lb = b.size();

        for (int d = min(la, lb); d >= 1; d--) {
            bool ok = true;
            for (int i = la - d, j = 0; i < la && j < lb; i++, j++)
                if (a[i] != b[j]) {
                    ok = false;

                    break;
                }

            if (ok)
                return d;
        }

        return 0;
    }

public:
    string shortestSuperstring(vector<string>& words) {
        const int n = words.size();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;

                w[i][j] = calc(words[i], words[j]);
            }

        memset(f, 0x3f, sizeof(f));

        for (int i = 0; i < n; i++) {
            f[1 << i][i] = words[i].size();
            g[1 << i][i] = -1;
        }

        for (int mask = 1; mask < (1 << n); mask++)
            for (int i = 0; i < n; i++) {
                if (!((mask >> i) & 1))
                    continue;

                for (int j = 0; j < n; j++) {
                    if ((mask >> j) & 1)
                        continue;

                    if (f[mask | 1 << j][j] > f[mask][i] + words[j].size() - w[i][j]) {
                        f[mask | 1 << j][j] = f[mask][i] + words[j].size() - w[i][j];
                        g[mask | 1 << j][j] = i;
                    }
                }
            }

        int len = INT_MAX, p;
        for (int i = 0; i < n; i++)
            if (len > f[(1 << n) - 1][i]) {
                len = f[(1 << n) - 1][i];
                p = i;
            }

        string ans;
        int mask = (1 << n) - 1;
        while (g[mask][p] != -1) {
            for (int i = words[p].size() - 1; i >= w[g[mask][p]][p]; i--)
                ans += words[p][i];

            int new_p = g[mask][p];
            mask ^= 1 << p;
            p = new_p;
        }

        for (int i = words[p].size() - 1; i >= 0; i--)
            ans += words[p][i];

        reverse(ans.begin(), ans.end());

        return ans;
    }
};