1. 项目概述：从“最短超串”到状态压缩DP的实战

最近在刷算法题时，遇到了一个挺有意思的经典难题：寻找最短超串。题目大意是，给你一组字符串，你需要找到一个最短的字符串，使得这组字符串中的每一个，都是这个“超级字符串”的子串。听起来有点像“求所有字符串的公共超集”，但难点在于，这个超串不是简单拼接，而是要最大化利用字符串之间的重叠部分来缩短总长度。比如给你["catg", "ctaagt", "gcta", "ttca"]，直接拼接起来很长，但如果你能找到它们之间的重叠顺序，像"gctaagttcatg"这样的串，就能把大家都包含进去，且长度最短。这问题在生物信息学的基因序列组装、数据压缩等领域都有实际应用，不是纯理论的玩具。

我最初尝试用贪心策略，每次都找重叠度最高的两个串合并，但很快就发现这得不到全局最优解。贪心算法在这里会陷入局部最优的陷阱。这让我意识到，必须用更系统的方法来枚举所有可能的排列组合，并计算每种排列下的最短超串长度。字符串数量一多，排列数就是阶乘级增长，暴力搜索根本不可行。这就是动态规划（DP）登场的时候了，但如何表示“哪些字符串已经被使用过”这个状态，成了关键。直接用一个数组或集合来记录，在状态转移时比较效率太低。这时，“状态压缩”技术就派上用场了——用一个整数的二进制位来表示一个集合，第i位为1表示第i个字符串已被使用。这种“状态压缩DP”是解决这类旅行商问题（TSP）变体的标准思路，也是本题的核心。

本文将详细拆解如何用C++实现这个算法。我会从问题重述和形式化定义开始，然后重点讲解状态压缩DP的设计思路，包括状态定义、转移方程、以及如何从DP表中回溯构造出最终的超串。我会提供完整的、可运行的C++代码，并附上详细的注释和调试方法。无论你是正在备战技术面试，还是对算法优化感兴趣，相信这个从问题分析到代码实现的完整过程，都能给你带来启发。

2. 核心思路与动态规划状态设计

解决“最短超串”问题，我们首先要把它转化成一个可以被动态规划处理的形式。核心的洞察在于：最终的超串，其构造过程可以看作是以某种顺序“访问”所有给定的字符串，并将它们依次拼接（或重叠合并）起来。我们的目标就是找到那个访问顺序，使得最终拼接出来的总长度最短。

2.1 问题形式化与预处理

假设我们有n个字符串，存放在数组words中。对于任意两个字符串words[i]和words[j]，我们定义overlap[i][j]为：将words[j]拼接到words[i]之后时，words[i]的后缀与words[j]的前缀的最大重叠长度。

例如，words[i] = "catg",words[j] = "atgct"。我们可以尝试不同的重叠长度：

• 重叠1个字符："catg"的最后一个字符g与"atgct"的第一个字符a不同，不行。
• 重叠2个字符："catg"的后两个"tg"与"atgct"的前两个"at"不同。
• 重叠3个字符："catg"的后三个"atg"与"atgct"的前三个"atg"相同。 因此，overlap[i][j] = 3。这意味着在最终超串中，如果i后面紧跟着j，那么words[j]只需要额外贡献len(j) - overlap[i][j] = 5 - 3 = 2个新字符。

计算所有i,j对的overlap是预处理的关键步骤。一个朴素的方法是对于每对(i, j)，枚举可能的重叠长度k(从min(len(i), len(j))向下枚举到0)，检查words[i]的后k个字符是否等于words[j]的前k个字符。一旦相等，就找到了最大重叠。这个预处理的时间复杂度是O(n^2 * L^2)，其中L是字符串的平均长度。在实际实现中，我们可以从可能的最大重叠开始尝试，一旦匹配成功就跳出循环，这样通常更快。

注意：这里有一个重要的边界情况，即i可能等于j。在状态转移中，我们不会将一个字符串接在自己后面，所以overlap[i][i]不会被用到，或者可以初始化为0。但更重要的是，题目给出的字符串列表中可能存在某个字符串已经是另一个字符串的子串。例如，words中包含"cat"和"catg"。那么"cat"就是"catg"的子串，任何包含"catg"的超串都自动包含了"cat"。一个有效的优化是，在预处理之前，先移除所有是其他字符串子串的字符串。这能减少问题规模n，极大提升DP效率。在代码实现中，这一步通常放在最前面。

2.2 状态压缩DP的状态定义

经过预处理，我们得到了overlap矩阵。现在问题转化为：我们需要找到一个0到n-1的排列p[0], p[1], ..., p[n-1]，使得以下总长度最小：总长度 = len(words[p[0]]) + Σ ( len(words[p[i]]) - overlap[p[i-1]][p[i]] )，其中i从1到n-1。 这个式子的意思是，第一个字符串贡献全部长度，之后每个字符串只贡献它除去与前一字符串重叠部分后的“新”长度。

如何用DP求解最优排列？我们定义dp[mask][i]：

• mask: 一个n位的二进制整数，用来表示当前已经使用了哪些字符串。如果第j位是1，表示字符串j已经被包含在当前构造的超串路径中了。
• i: 表示当前路径（即已构造的部分超串）的最后一个字符串是words[i]。
• dp[mask][i]的值：表示在已经使用了mask所表示的字符串集合，并且以words[i]结尾的情况下，所能达到的最短超串长度。

这里mask就是“状态压缩”的体现。原本需要用一个布尔数组或集合来表示“已使用”状态，现在用一个整数即可，使得状态可以作为数组的下标，极大地提升了查找和转移的效率。mask的范围是从0(没有使用任何字符串) 到(1 << n) - 1(使用了所有字符串)。

2.3 状态转移方程推导

初始状态是什么？当我们只使用一个字符串i时，mask = (1 << i)，此时的超串就是words[i]本身，所以dp[(1<<i)][i] = words[i].length()。

状态转移如何发生？假设我们当前的状态是(mask, i)，即我们已经构造了一条以i结尾的路径，包含了mask中的字符串。现在我们想扩展这条路径，加入一个尚未使用的新字符串j(即mask的第j位为0)。 新的状态mask_new就是mask | (1 << j)。 新的超串长度如何计算？新的超串是在旧超串后面拼接words[j]。由于我们已经知道overlap[i][j]，所以拼接j只需要增加len(j) - overlap[i][j]的长度。 因此，状态转移方程为：dp[mask_new][j] = min( dp[mask_new][j], dp[mask][i] + words[j].length() - overlap[i][j] )我们需要遍历所有可能的i(作为当前结尾) 和所有可能的j(作为下一个加入的字符串)，来更新DP表。

最终答案是什么？当mask变为全1（即(1<<n)-1），表示所有字符串都已使用时，我们遍历所有可能的结尾i，取dp[(1<<n)-1][i]中的最小值，即为最短超串的长度。

然而，题目要求输出超串本身，而不仅仅是长度。因此，我们还需要在DP的过程中，记录下达到每个最优状态(mask, i)时，它的前驱状态是哪个(prev_mask, prev_i)。这样，在找到最终的最短长度后，我们可以通过前驱信息一步步回溯，还原出字符串的拼接顺序，进而构造出最终的超串。

3. 算法实现细节与C++代码解析

理论清晰后，我们来看具体的C++实现。代码将分为几个主要部分：预处理（去子串、计算重叠）、动态规划填表、回溯构造答案。我会逐一解释关键代码段和其中的技巧。

3.1 预处理：去重与计算重叠矩阵

首先，我们实现一个辅助函数来计算两个字符串a和b的最大重叠长度（a的后缀与b的前缀）。

int calcOverlap(const string &a, const string &b) { int maxLen = min(a.size(), b.size()); // 从可能的最大重叠开始尝试，一旦成功立即返回 for (int len = maxLen; len > 0; --len) { if (a.substr(a.size() - len) == b.substr(0, len)) { return len; } } return 0; // 没有重叠 }

接下来是重要的预处理函数。它接收原始的words向量，返回处理后的新向量和重叠矩阵。

vector<string> preprocessWords(vector<string>& words) { vector<string> uniqueWords; int n = words.size(); vector<bool> isSubstr(n, false); // 1. 标记子串 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != j && words[i].size() <= words[j].size()) { // 如果 words[i] 是 words[j] 的子串 if (words[j].find(words[i]) != string::npos) { isSubstr[i] = true; break; // i 已经是某个字符串的子串，无需继续检查其他j } } } } // 2. 收集非子串的字符串 for (int i = 0; i < n; ++i) { if (!isSubstr[i]) { uniqueWords.push_back(words[i]); } } return uniqueWords; }

在主函数中，我们先调用preprocessWords，然后基于处理后的字符串列表计算overlap矩阵。

vector<string> validWords = preprocessWords(words); int n = validWords.size(); if (n == 0) return ""; // 所有字符串都是其他字符串的子串，任意返回一个即可 if (n == 1) return validWords[0]; // 只有一个字符串，它就是最短超串 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) { overlap[i][j] = calcOverlap(validWords[i], validWords[j]); } } }

3.2 动态规划表与路径记录

这是算法的核心部分。我们需要定义DP数组和前驱数组。由于mask的范围是0到(1<<n)-1，i的范围是0到n-1，所以DP数组是二维的。初始值设为无穷大（INT_MAX/2，防止加法溢出）。

const int INF = INT_MAX / 2; int totalStates = 1 << n; vector<vector<int>> dp(totalStates, vector<int>(n, INF)); vector<vector<int>> parent(totalStates, vector<int>(n, -1)); // 记录前驱字符串索引

初始化：每个字符串单独作为起点。

for (int i = 0; i < n; ++i) { dp[1 << i][i] = validWords[i].size(); // parent[1<<i][i] 保持为 -1，表示这是起点 }

状态转移：我们遍历所有可能的mask。对于每个mask，遍历所有可能的当前结尾i（要求mask包含i，即(mask >> i) & 1为真）。然后，遍历所有未使用的字符串j（(mask >> j) & 1为假），尝试从(mask, i)转移到(newMask, j)。

for (int mask = 0; mask < totalStates; ++mask) { for (int i = 0; i < n; ++i) { if ((mask & (1 << i)) == 0) continue; // i不在当前集合中，跳过 if (dp[mask][i] >= INF) continue; // 当前状态不可达，跳过 for (int j = 0; j < n; ++j) { if (mask & (1 << j)) continue; // j已经在集合中，跳过 int newMask = mask | (1 << j); int newLen = dp[mask][i] + validWords[j].size() - overlap[i][j]; if (newLen < dp[newMask][j]) { dp[newMask][j] = newLen; parent[newMask][j] = i; // 记录是从 i 转移到 j 的 } } } }

这里有一个重要的优化点：遍历mask的顺序。上面的代码是从0到totalStates-1顺序遍历。由于状态转移是从包含较少1的mask向包含较多1的mask进行，所以这个顺序是可行的。更精细的写法可以是按照mask中1的个数（即popcount）来分层遍历，但对于本题的数据范围（n <= 12或n <= 20是常见限制），顺序遍历的复杂度O(2^n * n^2)是可以接受的。

3.3 回溯构造最短超串

DP结束后，我们找到最终状态fullMask = (1 << n) - 1下，长度最小的那个结尾lastIdx。

int fullMask = (1 << n) - 1; int lastIdx = 0; int minLen = INF; for (int i = 0; i < n; ++i) { if (dp[fullMask][i] < minLen) { minLen = dp[fullMask][i]; lastIdx = i; } }

现在，我们从(fullMask, lastIdx)开始，利用parent数组向前回溯，还原出字符串的访问顺序（逆序）。

vector<int> path; int mask = fullMask; int cur = lastIdx; while (mask != 0) { path.push_back(cur); int prev = parent[mask][cur]; if (prev == -1) break; // 回溯到起点 mask ^= (1 << cur); // 从mask中移除当前字符串cur cur = prev; } reverse(path.begin(), path.end()); // 逆序得到正序的访问路径

得到路径path（例如[2, 0, 3, 1]）后，我们就可以构造超串了。第一个字符串全部加入，之后的每个字符串，只添加其不重叠的部分。

string result = validWords[path[0]]; for (int idx = 1; idx < path.size(); ++idx) { int prev = path[idx - 1]; int curr = path[idx]; int ov = overlap[prev][curr]; result += validWords[curr].substr(ov); // 只添加重叠部分之后的内容 } return result;

3.4 完整代码整合与测试

将上述所有部分整合，就得到了完整的解决方案。这里给出一个整合后的函数签名和简要结构：

class Solution { public: string shortestSuperstring(vector<string>& words) { // 1. 预处理，移除子串 vector<string> validWords = preprocessWords(words); int n = validWords.size(); if (n == 0) return words[0]; // 或返回空串，依题意 if (n == 1) return validWords[0]; // 2. 计算重叠矩阵 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) { overlap[i][j] = calcOverlap(validWords[i], validWords[j]); } } } // 3. 状态压缩DP const int INF = INT_MAX / 2; int totalStates = 1 << n; vector<vector<int>> dp(totalStates, vector<int>(n, INF)); vector<vector<int>> parent(totalStates, vector<int>(n, -1)); // 初始化 for (int i = 0; i < n; ++i) { dp[1 << i][i] = validWords[i].size(); } // 状态转移 for (int mask = 0; mask < totalStates; ++mask) { for (int i = 0; i < n; ++i) { if (!(mask & (1 << i)) || dp[mask][i] >= INF) continue; for (int j = 0; j < n; ++j) { if (mask & (1 << j)) continue; int newMask = mask | (1 << j); int newLen = dp[mask][i] + validWords[j].size() - overlap[i][j]; if (newLen < dp[newMask][j]) { dp[newMask][j] = newLen; parent[newMask][j] = i; } } } } // 4. 找到最优解结尾 int fullMask = (1 << n) - 1; int lastIdx = 0; for (int i = 1; i < n; ++i) { if (dp[fullMask][i] < dp[fullMask][lastIdx]) { lastIdx = i; } } // 5. 回溯构造路径 vector<int> path; int mask = fullMask; int cur = lastIdx; while (mask) { path.push_back(cur); int prev = parent[mask][cur]; if (prev == -1) break; mask ^= (1 << cur); cur = prev; } reverse(path.begin(), path.end()); // 6. 根据路径构造超串 string ans = validWords[path[0]]; for (int i = 1; i < path.size(); ++i) { int prev = path[i-1]; int curr = path[i]; ans += validWords[curr].substr(overlap[prev][curr]); } return ans; } private: // calcOverlap 和 preprocessWords 函数定义同上 ... };

你可以用题目示例["catg","ctaagt","gcta","ttca"]测试，应该得到"gctaagttcatg"。也可以用["alex","loves","leetcode"]测试，得到"alexlovesleetcode"（注意这里没有重叠，就是简单拼接）。

4. 复杂度分析与优化探讨

实现完成后，我们需要分析算法的时间和空间复杂度，并讨论可能的优化方向。

4.1 时间复杂度分析

1. 预处理：
   • 去子串操作：最坏情况下需要两两比较，时间复杂度为O(n^2 * L)，其中L是字符串平均长度，find操作可以认为是O(L)。
   • 计算重叠矩阵：对于n个字符串，需要计算O(n^2)对重叠。每对重叠的计算，最坏需要比较min(L_i, L_j)次，每次比较是O(L)（substr和字符串比较）。因此，这部分是O(n^2 * L^2)。在实际中，由于我们是从最大可能重叠开始尝试，一旦匹配成功就停止，平均情况会好很多。
2. 动态规划：
   • 状态数：O(2^n * n)。mask有2^n种，对于每个mask，我们需要考虑最多n个可能的结尾i。
   • 状态转移：对于每个状态(mask, i)，我们需要尝试所有未使用的j（最多n个）进行转移。
   • 因此，DP部分的时间复杂度是O(2^n * n^2)。

综合来看，整个算法的时间复杂度主要由DP部分主导，为O(2^n * n^2)。这在n <= 12时（状态数约2^12 * 12^2 ≈ 600k）是完全可以接受的。当n达到 20 时，2^20 ≈ 1e6，再乘以n^2=400，运算量达到4e8，在普通机器上就可能超时（>1秒）。因此，这个算法适用于n较小（通常 <= 16）的场景。

4.2 空间复杂度分析

1. DP表：dp数组大小为2^n * n，每个元素是int，空间复杂度为O(2^n * n)。
2. 前驱表：parent数组大小相同，也是O(2^n * n)。
3. 重叠矩阵：overlap矩阵大小为n * n，空间复杂度为O(n^2)。

因此，总的空间复杂度为O(2^n * n + n^2)。对于n=12，2^12=4096，4096*12 ≈ 50k，两个表加起来约100k个int，约0.4MB，内存消耗很小。但当n=20时，2^20=1,048,576，1M*20 ≈ 20M个状态，每个int4字节，仅DP表就需要约80MB，加上前驱表就超过160MB，这可能超出一些在线判题系统的内存限制。因此，空间也是限制n不能太大的一个重要因素。

4.3 潜在优化方向

尽管状态压缩DP已经是解决此类排列优化问题的标准且高效的方法，但在面对极限数据时，我们还可以考虑一些优化：

1. 剪枝与启发式：在DP转移前，可以对字符串进行排序或使用启发式规则（如长度、公共前缀等）来优先处理更可能产生大重叠的转移，虽然不能改变最坏复杂度，但可能提升平均速度。
2. 记忆化搜索（DFS+Memoization）：有时用递归+记忆化的方式实现DP，代码可能更清晰，并且可以结合深度优先搜索的特性，配合上下界剪枝（例如，当前长度加上剩余字符串的最小可能增长长度如果已经超过已知最优解，则剪枝），这在某些情况下比递推更快。
3. 迭代加深或分支定界：对于更大的n，精确算法可能不再适用。可以考虑使用近似算法，如迭代局部搜索、模拟退火或遗传算法，来寻找一个接近最优的解。题目如果只要求近似解，这是一个方向。
4. 使用更紧凑的状态表示：如果只求最短长度而不需要构造路径，parent数组可以省略。此外，有些实现使用dp[mask]只记录到达该mask的最短长度，而用另一个数组last[mask]记录最后一个字符串，但这样在回溯构造路径时会麻烦一些。
5. 使用整数运算优化：判断mask中是否包含某位、计算新mask等操作，使用位运算 (&,|,^,<<) 是极其高效的，这也是状态压缩的核心优势之一。

对于在线判题（OJ）环境，通常题目会明确限制n的范围（例如1 <= n <= 12），使得O(2^n * n^2)的算法成为标答。我们的实现已经足够应对。

5. 调试技巧与常见问题排查

在实现这样一个涉及位运算和动态规划的状态压缩算法时，很容易遇到一些棘手的bug。以下是我在编写和调试过程中总结的一些经验和常见问题。

5.1 初始化与边界条件

• DP数组初始值：务必设置为一个足够大的数（如INT_MAX/2），表示“不可达”或“无穷大”。使用INT_MAX时要小心，因为在状态转移中会做加法dp[mask][i] + len(j) - overlap，可能导致整数溢出变成负数。用INT_MAX/2是更安全的做法。
• 起点状态初始化：dp[1<<i][i] = words[i].size()必须正确设置。确保1 << i在整数范围内（i < 32对于32位int）。
• 空输入或单字符串输入：这是常见的边界情况。如果预处理后n=0（所有字符串都是其他字符串的子串），按照题目要求，通常返回任意一个原字符串即可。如果n=1，直接返回该字符串。代码开头就要处理这些情况。

5.2 状态转移的逻辑错误

• mask的遍历顺序：虽然从0到totalStates-1的顺序遍历在理论上是正确的（因为newMask一定比mask大），但确保在访问dp[mask][i]时，它已经被计算过。我们的写法（先遍历所有mask）是安全的。如果使用记忆化搜索，则无需关心顺序。
• 重复转移与自我转移：内层循环一定要判断if (mask & (1 << j)) continue;防止将同一个字符串j重复加入路径。同时，i和j不能相同（i != j），这已经在计算overlap矩阵时体现（overlap[i][i]未被使用或为0），在转移时由于j不在mask中，自然也不会发生i==j的转移。
• 前驱记录：parent[newMask][j] = i;这行代码必须在更新dp[newMask][j]时同步执行。这是为了记录达到(newMask, j)这个最优状态时，它的前一个字符串是i。如果只更新dp值而不更新parent，回溯时会出错。

5.3 回溯构造路径的陷阱

• 回溯终止条件：while (mask)循环中，当mask变为0时停止。但我们需要小心处理起点。在回溯时，parent[mask][cur]为-1表示cur是路径中的第一个字符串。此时我们应该将cur加入path，然后跳出循环。代码中的if (prev == -1) break;就是处理这种情况。另一种写法是在初始化时，将起点的parent设为一个特殊值（如-1），并在回溯时判断。
• mask的更新：在回溯中，我们需要从当前状态mask中移除当前字符串cur，以回到前一个状态。正确的操作是mask ^= (1 << cur)（将第cur位取反）或者mask &= ~(1 << cur)（将第cur位清0）。使用mask -= (1 << cur)在逻辑上正确，但位运算是更清晰和高效的做法。
• 路径顺序：回溯得到的是逆序路径（从最后一个字符串到第一个），所以最后需要reverse(path.begin(), path.end())。

5.4 重叠计算与字符串操作

• calcOverlap函数的效率：在计算重叠时，我们使用了substr方法。substr会生成新的临时字符串，有一定开销。对于性能要求极高的场景，可以改为直接比较字符，避免创建子串。

  int calcOverlap(const string &a, const string &b) { int maxLen = min(a.size(), b.size()); for (int len = maxLen; len > 0; --len) { bool ok = true; for (int k = 0; k < len; ++k) { if (a[a.size() - len + k] != b[k]) { ok = false; break; } } if (ok) return len; } return 0; }

• 子串去重逻辑：preprocessWords中，判断words[i]是否是words[j]的子串，我们使用了words[j].find(words[i])。这里要注意，当i==j时，find会返回0（自己当然是自己的子串），所以必须加上i != j的条件。同时，我们只当words[i].size() <= words[j].size()时才进行检查，这是一个小优化。

5.5 调试输出与可视化

对于复杂的DP，添加调试输出是理解程序运行过程、定位错误的好方法。可以在关键位置打印信息：

// 例如，在状态转移后打印某个状态的变化 if (mask == someSpecificMask && i == someSpecificI && j == someSpecificJ) { cout << "dp[" << bitset<4>(mask) << "][" << i << "]=" << dp[mask][i] << " -> dp[" << bitset<4>(newMask) << "][" << j << "]=" << newLen << endl; } // 或者，在回溯完成后打印路径 cout << "Path: "; for (int idx : path) cout << idx << " "; cout << endl;

对于小规模输入（如n=4），你甚至可以打印出整个DP表，观察其填充过程，这能帮你验证状态定义和转移方程是否正确。

最后，多使用题目提供的示例和自编的小例子进行测试。从最简单的两个字符串开始（["ab", "bc"]，答案应为"abc"），逐步增加复杂度，确保每一步的输出都符合预期。