leetcode 943

问题

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

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

Example 2:

1
2
Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

  1. 1 <= A.length <= 12
  2. 1 <= A[i].length <= 20

分析

思路1：使用搜索算法（DFS/Backtracking），但是要注意进行剪枝和预处理，$cost[i][j]$ 表示将 $A[j]$ 接在 $A[i]$ 后面最多还要追加多少个单词。另外还要注意在DFS的过程中，只记录路径即可，不要来记录具体的字符串，这样也可以节省很多的时间。

思路2: 采用DP算法，采用和思路1相同的 $cost[i][j]$ 。题目可以看作是有 $n$ 个节点，每个节点仅访问一次，求最小$cost$ 并给出具体的路径。采用二进制压缩的DP来记录已经访问过的节点有哪些，以及在该访问状态下最后一个被访问的节点是哪个。同时使用 $parent[i][j]$ 该状态的前一个状态是哪个（只需要记录上一个状态下最后一个被访问的节点即可）。

NOTE: 疑问，会不会存在问题？？比如 “a” + “cost” + “acost”? 应该是5，这样算出来是10？？

当然上述问题不会存在，因为题目中特地强调了，字符串数组A中的任何一个字符串都不是其他字符串的子串。

代码1

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 1860 ms  偶尔提交会超时
class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        int n = A.size();
        vector<vector<int>> cost(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cost[i][j] = A[j].size();
                if (j == i) continue;
                int len = min(A[i].size(), A[j].size());
                for (int k = 1; k < len; ++k) {
                    if (A[i].substr(A[i].size()-k) == A[j].substr(0, k))
                        cost[i][j] = A[j].size()-k;
                }
            }
        }
        vector<int> path, curPath;
        int maxCost = INT_MAX;
        dfs(path, curPath, maxCost, 0, 0, cost);
        string ans = A[path[0]];
        for (int i = 1; i < path.size(); ++i) {
            int index = path[i];
            int lastIndex = path[i-1];
            int c = cost[lastIndex][index];
            ans += A[index].substr(A[index].size()-c);
        }
        return ans;
    }

    void dfs(vector<int> &path, vector<int> &curPath,
            int &maxCost, int curCost, int used, vector<vector<int>> &cost) {
        int n = cost.size();
        if (curCost >= maxCost)
            return;
        if (curPath.size() == n) {
            maxCost = curCost;
            path = curPath;
            return;
        }
        if (curPath.size() == 0) {
            for (int i = 0; i < n; ++i) {
                curPath.push_back(i);
                dfs(path, curPath, maxCost, cost[i][i], used|(1<<i), cost);
                curPath.pop_back();
            }
        } else {
            int lastPoint = curPath.back();
            for (int i = 0; i < n; ++i) {
                if (used&(1<<i)) continue;
                curPath.push_back(i);
                dfs(path, curPath, maxCost, curCost+cost[lastPoint][i], used|(1<<i), cost);
                curPath.pop_back();
            }
        }
    }
};

代码2

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        int n = A.size();
        vector<vector<int>> cost(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cost[i][j] = A[j].size();
                if (j == i) continue;
                int len = min(A[i].size(), A[j].size());
                for (int k = 1; k < len; ++k) {
                    if (A[i].substr(A[i].size()-k) == A[j].substr(0, k))
                        cost[i][j] = A[j].size()-k;
                }
            }
        }
        vector<vector<int>> dp(1<<n, vector<int>(n, INT_MAX/2));
        vector<vector<int>> parent(1<<n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            dp[1<<i][i] = A[i].size();
        }
        for (int i = 0; i < (1<<n); ++i) {
            for (int j = 0; j < n; ++j) {
                if (((1<<j)&i) == 0) continue;
                for (int p = 0; p < n; ++p) {
                    if (j == p || ((1<<p)&i) == 0) continue;
                    int prev = i&(~(1<<j));
                    if (dp[prev][p] + cost[p][j] < dp[i][j]) {
                        dp[i][j] = dp[prev][p] + cost[p][j];
                        parent[i][j] = p;
                    }
                }
            }
        }
        int last = 0;
        int maxCost = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (maxCost > dp[(1<<n)-1][i]) {
                last = i;
                maxCost = dp[(1<<n)-1][i];
            }
        }
        string ans = A[last];
        for (int i = 0, state = (1<<n)-1; i < n-1; ++i) {
            int j = parent[state][last];
            int size = A[j].size() - (A[last].size() - cost[j][last]);
            ans = A[j].substr(0, size) + ans;
            state = state & ~(1<<last);
            last = j;
        }

        return ans;
    }
};