最短超级串Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个字符串数组 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 中的所有字符串互不相同

# 思路

// 状态压缩(将字符串记录也压缩) + dp + 字典树

# 解法


class Solution {
    // 状态压缩(将字符串记录也压缩) + dp + 字典树


    public String shortestSuperstring(String[] words) {
        int n = words.length, f = (1 << n) - 1;
        List<Integer>[] lists = new ArrayList[n + 1];
        for (int i = 1; i <= f; i++) {
            int j = 0, k = i;
            while (k > 0) {
                k &= (k-1);
                j++;
            }
            if (lists[j] == null) {
                lists[j] = new ArrayList<>();
            }
            lists[j].add(i);
        }
        int[][] let = searchPrefix(words);
        long[] dp = new long[(1 << (n + 4)) - 1];
        for (int i = 0; i < n; i++) {
            dp[(n << n) | 1 << i] = i;
        }
        for (Integer integer : lists[1]) {
            int bit = integer & (~integer + 1);
            int j = (int) dp[(n << n) | bit] , len = words[j].length();
            dp[(j << n) | integer] = ((long) j << 9) | len;
        }
        for (int i = 2; i <= n; i++) {
            for (int integer : lists[i]) {
                int integer_ = integer;
                while (integer_ > 0) {
                    int bit = integer_ & (~integer_ + 1);
                    int j = (int) dp[(n << n) | bit], t = integer ^ bit, t_ = t, min = Integer.MAX_VALUE;
                    while (t > 0) {
                        int bit_ = t & (~t + 1);
                        int k = (int) dp[(n << n) | bit_];
                        long dp_ = dp[(k << n) | t_];
                        int len = words[j].length() + (int) (dp_ & ((1L << 9) - 1)) - let[j][k];
                        if (len < min) {
                            dp_ >>= 9;
                            dp_ <<= 4;
                            dp_ |= j;
                            dp[(j << n) | integer] = (dp_ << 9) | len;
                            min = len;
                        }
                        t ^= bit_;
                    }
                    integer_ ^= bit;
                }

            }
        }
        int min = Integer.MAX_VALUE, index = 0;
        for (int i = 0; i < n; i++) {
            int j = i << n | f, len = (int) (dp[j] & ((1 << 9) - 1));
            if (len < min) {
                index = j;
                min = len;
            }
        }
        StringBuilder sb = new StringBuilder();
        long t = dp[index] >> 9;
        int q = (int) (t & ((1 << 4) - 1));
        sb.append(words[q]);
        t >>= 4;
        for (int i = 1; i < n; i++) {
            int p = (int) (t & ((1 << 4) - 1));
            sb.append(words[p].substring(let[q][p]));
            q = p;
            t >>= 4;
        }
        return sb.toString();
    }
    private int[][] searchPrefix(String[] words) {
        Trie t = new Trie();
        int n = words.length;
        for (int i = 0; i < n; i++) {
            t.insert(words[i], i);
        }
        int[][] let = new int[n][n];
        for (int i = 0; i < n; i++) {
            int len = words[i].length();
            for (int j = 0; j < len; j++) {
                List<Integer> search = t.search(words[i], j);
                for (Integer index : search) {
                    let[i][index] = Math.max(let[i][index], len - j);
                }
            }
        }
        return let;
    }
}
class Trie {
    private Trie[] children;
    private List<Integer> indexs;

    public Trie() {
        children = new Trie[26];
        indexs = new ArrayList<>();
    }

    public void insert(String word, int f) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
            node.indexs.add(f);
        }
    }

    public List<Integer> search(String word, int l) {
        Trie node = searchPrefix(word, l);
        return node == null ? new ArrayList<>() : node.indexs;
    }

    private Trie searchPrefix(String prefix, int l) {
        Trie node = this;
        for (int i = l; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

# 总结

分析出几种情况，然后分别对各个情况实现

#Java