动态规划-TSP问题-最短超级串

2020-03-03 22:55:08

问题描述：

给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。

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

示例 1：

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

示例 2：

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

提示：

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

问题求解：

解法一：暴力求解

首先我们要明确的就是，本题可以转化成图论的题目，就是在一个图中要遍历所有的节点一次，最后路径的最小值是多少。（这里和TSP略有不同，即我们不需要返回起始节点）

暴力求解，可以理解为全排列，只不过我们做了一些剪枝操作进行了加速。

时间复杂度：O(n!)

    int res = (int)1e9;

    List<Integer> path;

    int n;

    public String shortestSuperstring(String[] A) {

        n = A.length;

        int[][] graph = new int[n][n];

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

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

                for (int k = Math.min(A[i].length(), A[j].length()); k >= 0; k--) {

                    if (A[j].substring(0, k).equals(A[i].substring(A[i].length() - k))) {

                        graph[i][j] = A[j].length() - k;

                        break;

                    }

                }

            }

        }

        helper(A, graph, 0, 0, 0, new ArrayList<>());

        StringBuffer sb = new StringBuffer();

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

            int node = path.get(i);

            String s = A[node];

            if (i == 0) sb.append(s);

            else sb.append(s.substring(s.length() - graph[path.get(i - 1)][node]));

        }

        return sb.toString();

    }

    private void helper(String[] A, int[][] graph, int k, int used, int curr, List<Integer> curr_p) {

        if (curr >= res) return;

        if (k == n) {

            res = curr;

            path = new ArrayList<>(curr_p);

            return;

        }

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

            if ((used & (1 << i)) != 0) continue;

            curr_p.add(i);

            helper(A, graph, k + 1, used | (1 << i), k == 0 ? A[i].length() : curr + graph[curr_p.get(curr_p.size() - 2)][i], curr_p);

            curr_p.remove(curr_p.size() - 1);

        }

    }

解法二：DP

dp[s][i] : 当前访问过的节点状态为s，且以i为结尾的最短路径。

init :

dp[1 << i][i] = A[i].length()

transition :

对于dp[s][i]我们需要去枚举所有的parent节点，计算得到当前的最小值。

dp[s][i] = min{dp[s - (1 << i)][j] + graph[j][i]) 将A[i]追加到A[j]后面。

时间复杂度：O(2 ^n * n ^ 2) 同TSP问题

    public String shortestSuperstring(String[] A) {

        int n = A.length;

        int[][] graph = new int[n][n];

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

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

                for (int k = Math.min(A[i].length(), A[j].length()); k >= 0; k--) {

                    if (A[j].substring(0, k).equals(A[i].substring(A[i].length() - k))) {

                        graph[i][j] = A[j].length() - k;

                        break;

                    }

                }

            }

        }

        int[][] dp = new int[1 << n][n];

        int[][] parent = new int[1 << n][n];

        for (int i = 0; i < 1 << n; i++) {

            Arrays.fill(dp[i], (int)1e9);

            Arrays.fill(parent[i], -1);

        }

        for (int i = 0; i < n; i++) dp[1 << i][i] = A[i].length();

        for (int s = 1; s < 1 << n; s++) {

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

                if ((s & (1 << i)) == 0) continue;

                int prev = s - (1 << i);

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

                    if (dp[prev][j] + graph[j][i] < dp[s][i]) {

                        dp[s][i] = dp[prev][j] + graph[j][i];

                        parent[s][i] = j;

                    }

                }

            }

        }

        int curr = -1;

        int min = (int)1e9;

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

            if (dp[(1 << n) - 1][i] < min) {

                min = dp[(1 << n) - 1][i];

                curr = i;

            }

        }

        int s = (1 << n) - 1;

        String res = "";

        while (s > 0) {

            int prev = parent[s][curr];

            if (prev == -1) res = A[curr] + res;

            else res = A[curr].substring(A[curr].length() - graph[prev][curr]) + res;

            s &= ~(1 << curr);

            curr = prev;

        }

        return res;

    }

巴特西

动态规划-TSP问题-最短超级串

最新文章

热门文章