题目

给定一个字符串数组 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;
    }
}

总结

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