943.最短超级串

最短超级串

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

示例 1:

输入：words = [“alex”,”loves”,”leetcode”]
输出：”alexlovesleetcode”

提示:

• 1 <= words.length <= 12
• 1 <= words[i].length <= 20
• words[i] 由小写字母组成
• words 中没有字符串是另一个字符串的子字符串

解析

使用状态压缩动态规划，计算字符串之间的重叠长度，然后 DP 找出最优顺序。

var shortestSuperstring = function (words) {
  const n = words.length;
  const overlap = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j) {
        let len = Math.min(words[i].length, words[j].length);
        while (len > 0 && !words[j].startsWith(words[i].slice(-len))) {
          len--;
        }
        overlap[i][j] = len;
      }
    }
  }

  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
  const parent = Array.from({ length: 1 << n }, () => new Array(n).fill(-1));

  for (let i = 0; i < n; i++) {
    dp[1 << i][i] = words[i].length;
  }

  for (let mask = 1; mask < 1 << n; mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      const prevMask = mask ^ (1 << last);
      if (prevMask === 0) continue;

      for (let prev = 0; prev < n; prev++) {
        if (!(prevMask & (1 << prev))) continue;
        const value = dp[prevMask][prev] + words[last].length - overlap[prev][last];
        if (value < dp[mask][last]) {
          dp[mask][last] = value;
          parent[mask][last] = prev;
        }
      }
    }
  }

  let mask = (1 << n) - 1;
  let last = dp[mask].indexOf(Math.min(...dp[mask]));
  const order = [];

  while (mask) {
    order.unshift(last);
    const prev = parent[mask][last];
    mask ^= 1 << last;
    last = prev;
  }

  let result = words[order[0]];
  for (let i = 1; i < order.length; i++) {
    result += words[order[i]].slice(overlap[order[i - 1]][order[i]]);
  }

  return result;
};

时间复杂度 O(n² * 2^n)，空间复杂度 O(n * 2^n)。