Hard
题目描述
给定一个字符串数组 words，返回一个包含数组中每个字符串作为子字符串的最小字符串。如果有多个长度最小的有效字符串，返回其中任意一个即可。
可以假设 words 中没有字符串是另一个字符串的子字符串。
示例 1：
输入：words = ["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex","loves","leetcode" 的所有排列都可以被接受。
示例 2：
输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"
提示：
1 <= words.length <= 121 <= words[i].length <= 20words[i]由小写英文字母组成words的所有字符串都是唯一的
解题思路
这是一个典型的旅行商问题的变种，可以使用动态规划+状态压缩来解决。
核心思路：
预处理重叠信息：计算每两个字符串之间的最大重叠长度。如果字符串A的后缀与字符串B的前缀有重叠，记录重叠的长度。
状态设计：使用位掩码表示已经使用的字符串集合，
dp[mask][i]表示使用了mask集合中的字符串且以第i个字符串结尾的最短超级字符串长度。状态转移：对于每个状态，尝试添加一个新的字符串，利用预计算的重叠信息来减少总长度。
路径记录：在DP过程中记录每个状态的前驱，最后通过回溯构造出最短超级字符串。
算法步骤：
- 预计算任意两个字符串间的重叠长度
- 使用状态压缩DP找到最短路径
- 回溯构造最终的超级字符串
这种方法的时间复杂度是O(n²×2ⁿ)，空间复杂度是O(n×2ⁿ)，适合处理字符串数量不超过12的情况。
代码实现
class Solution {
public:
string shortestSuperstring(vector<string>& words) {
int n = words.size();
// 计算重叠长度
vector<vector<int>> overlap(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
int maxLen = min(words[i].length(), words[j].length());
for (int k = maxLen; k >= 1; k--) {
if (words[i].substr(words[i].length() - k) == words[j].substr(0, k)) {
overlap[i][j] = k;
break;
}
}
}
}
}
// DP: dp[mask][i] = 使用mask集合中的字符串且以i结尾的最短长度
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
vector<vector<int>> parent(1 << n, vector<int>(n, -1));
// 初始化：只使用一个字符串
for (int i = 0; i < n; i++) {
dp[1 << i][i] = words[i].length();
}
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;
for (int v = 0; v < n; v++) {
if (mask & (1 << v)) continue;
int newMask = mask | (1 << v);
int newLen = dp[mask][u] + words[v].length() - overlap[u][v];
if (newLen < dp[newMask][v]) {
dp[newMask][v] = newLen;
parent[newMask][v] = u;
}
}
}
}
// 找到最优解
int finalMask = (1 << n) - 1;
int minLen = INT_MAX;
int last = -1;
for (int i = 0; i < n; i++) {
if (dp[finalMask][i] < minLen) {
minLen = dp[finalMask][i];
last = i;
}
}
// 重构路径
vector<int> path;
int mask = finalMask;
int curr = last;
while (curr != -1) {
path.push_back(curr);
int prev = parent[mask][curr];
mask ^= (1 << curr);
curr = prev;
}
reverse(path.begin(), path.end());
// 构造结果字符串
string result = words[path[0]];
for (int i = 1; i < path.size(); i++) {
int prev = path[i-1];
int curr = path[i];
result += words[curr].substr(overlap[prev][curr]);
}
return result;
}
};
class Solution:
def shortestSuperstring(self, words: List[str]) -> str:
n = len(words)
# 计算重叠长度
overlap = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i != j:
max_len = min(len(words[i]), len(words[j]))
for k in range(max_len, 0, -1):
if words[i].endswith(words[j][:k]):
overlap[i][j] = k
break
# DP: dp[mask][i] = 使用mask集合中的字符串且以i结尾的最短长度
dp = [[float('inf')] * n for _ in range(1 << n)]
parent = [[-1] * n for _ in range(1 << n)]
# 初始化：只使用一个字符串
for i in range(n):
dp[1 << i][i] = len(words[i])
for mask in range(1, 1 << n):
for u in range(n):
if not (mask & (1 << u)) or dp[mask][u] == float('inf'):
continue
for v in range(n):
if mask & (1 << v):
continue
new_mask = mask | (1 << v)
new_len = dp[mask][u] + len(words[v]) - overlap[u][v]
if new_len < dp[new_mask][v]:
dp[new_mask][v] = new_len
parent[new_mask][v] = u
# 找到最优解
final_mask = (1 << n) - 1
min_len = float('inf')
last = -1
for i in range(n):
if dp[final_mask][i] < min_len:
min_len = dp[final_mask][i]
last = i
# 重构路径
path = []
mask = final_mask
curr = last
while curr != -1:
path.append(curr)
prev = parent[mask][curr]
mask ^= (1 << curr)
curr = prev
path.reverse()
# 构造结果字符串
result = words[path[0]]
for i in range(1, len(path)):
prev = path[i-1]
curr = path[i]
result += words[curr][overlap[prev][curr]:]
return result
public class Solution {
public string ShortestSuperstring(string[] words) {
int n = words.Length;
// 计算重叠长度
int[,] overlap = new int[n, n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
int maxLen = Math.Min(words[i].Length, words[j].Length);
for (int k = maxLen; k >= 1; k--) {
if (words[i].Substring(words[i].Length - k) == words[j].Substring(0, k)) {
overlap[i, j] = k;
break;
}
}
}
}
}
// DP: dp[mask][i] = 使用mask集合中的字符串且以i结尾的最短长度
int[,] dp = new int[1 << n, n];
int[,] parent = new int[1 << n, n];
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
dp[i, j] = int.MaxValue;
parent[i, j] = -1;
}
}
// 初始化：只使用一个字符串
for (int i = 0; i < n; i++) {
dp[1 << i, i] = words[i].Length;
}
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask, u] == int.MaxValue) continue;
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue;
int newMask = mask | (1 << v);
int newLen = dp[mask, u] + words[v].Length - overlap[u, v];
if (newLen < dp[newMask, v]) {
dp[newMask, v] = newLen;
parent[newMask, v] = u;
}
}
}
}
// 找到最优解
int finalMask = (1 << n) - 1;
int minLen = int.MaxValue;
int last = -1;
for (int i = 0; i < n; i++) {
if (dp[finalMask, i] < minLen) {
minLen = dp[finalMask, i];
last = i;
}
}
// 重构路径
List<int> path = new List<int>();
int mask = finalMask;
int curr = last;
while (curr != -1) {
path.Add(curr);
int prev = parent[mask, curr];
mask ^= (1 << curr);
curr = prev;
}
path.Reverse();
// 构造结果字符串
StringBuilder result = new StringBuilder(words[path[0]]);
for (int i = 1; i < path.Count; i++) {
int prev = path[i-1];
int current = path[i];
result.Append(words[current].Substring(overlap[prev, current]));
}
return result.ToString();
}
}
var shortestSuperstring = function(words) {
const n = words.length;
// Calculate overlap between word i and word j (when i comes before j)
const overlap = Array(n).fill().map(() => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j) continue;
let maxOverlap = 0;
const minLen = Math.min(words[i].length, words[j].length);
for (let k = 1; k <= minLen; k++) {
if (words[i].slice(-k) === words[j].slice(0, k)) {
maxOverlap = k;
}
}
overlap[i][j] = maxOverlap;
}
}
// DP with bitmask
// dp[mask][i] = minimum length to visit all words in mask ending at word i
const dp = Array(1 << n).fill().map(() => Array(n).fill(Infinity));
const parent = Array(1 << n).fill().map(() => Array(n).fill(-1));
// Initialize: start with each word
for (let i = 0; i < n; i++) {
dp[1 << i][i] = words[i].length;
}
for (let mask = 1; mask < (1 << n); mask++) {
for (let i = 0; i < n; i++) {
if (!(mask & (1 << i))) continue;
if (dp[mask][i] === Infinity) continue;
for (let j = 0; j < n; j++) {
if (mask & (1 << j)) continue;
const newMask = mask | (1 << j);
const newLength = dp[mask][i] + words[j].length - overlap[i][j];
if (newLength < dp[newMask][j]) {
dp[newMask][j] = newLength;
parent[newMask][j] = i;
}
}
}
}
// Find the ending word that gives minimum length
const finalMask = (1 << n) - 1;
let minLength = Infinity;
let lastWord = -1;
for (let i = 0; i < n; i++) {
if (dp[finalMask][i] < minLength) {
minLength = dp[finalMask][i];
lastWord = i;
}
}
// Reconstruct the path
const path = [];
let mask = finalMask;
let curr = lastWord;
while (curr !== -1) {
path.push(curr);
const prev = parent[mask][curr];
mask ^= (1 << curr);
curr = prev;
}
path.reverse();
// Build the result string
let result = words[path[0]];
for (let i = 1; i < path.length; i++) {
const prev = path[i - 1];
const curr = path[i];
result += words[curr].slice(overlap[prev][curr]);
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n² × 2ⁿ + n² × L) - 其中n是字符串数量，L是字符串的平均长度。预处理重叠信息需要O(n² × L)，DP需要O(n² × 2ⁿ) |
| 空间复杂度 | O(n × 2ⁿ + n²) - DP表需要O(n × 2ⁿ)空间，重叠矩阵需要O(n²)空间 |