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[(1i)][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即(1n)-1表示所有字符串都已使用时我们遍历所有可能的结尾i取dp[(1n)-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向量返回处理后的新向量和重叠矩阵。vectorstring preprocessWords(vectorstring words) { vectorstring uniqueWords; int n words.size(); vectorbool 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矩阵。vectorstring validWords preprocessWords(words); int n validWords.size(); if (n 0) return ; // 所有字符串都是其他字符串的子串任意返回一个即可 if (n 1) return validWords[0]; // 只有一个字符串它就是最短超串 vectorvectorint overlap(n, vectorint(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到(1n)-1i的范围是0到n-1所以DP数组是二维的。初始值设为无穷大INT_MAX/2防止加法溢出。const int INF INT_MAX / 2; int totalStates 1 n; vectorvectorint dp(totalStates, vectorint(n, INF)); vectorvectorint parent(totalStates, vectorint(n, -1)); // 记录前驱字符串索引初始化每个字符串单独作为起点。for (int i 0; i n; i) { dp[1 i][i] validWords[i].size(); // parent[1i][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数组向前回溯还原出字符串的访问顺序逆序。vectorint 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(vectorstring words) { // 1. 预处理移除子串 vectorstring validWords preprocessWords(words); int n validWords.size(); if (n 0) return words[0]; // 或返回空串依题意 if (n 1) return validWords[0]; // 2. 计算重叠矩阵 vectorvectorint overlap(n, vectorint(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; vectorvectorint dp(totalStates, vectorint(n, INF)); vectorvectorint parent(totalStates, vectorint(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. 回溯构造路径 vectorint 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 时间复杂度分析预处理去子串操作最坏情况下需要两两比较时间复杂度为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)。在实际中由于我们是从最大可能重叠开始尝试一旦匹配成功就停止平均情况会好很多。动态规划状态数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^2400运算量达到4e8在普通机器上就可能超时1秒。因此这个算法适用于n较小通常 16的场景。4.2 空间复杂度分析DP表dp数组大小为2^n * n每个元素是int空间复杂度为O(2^n * n)。前驱表parent数组大小相同也是O(2^n * n)。重叠矩阵overlap矩阵大小为n * n空间复杂度为O(n^2)。因此总的空间复杂度为O(2^n * n n^2)。对于n122^1240964096*12 ≈ 50k两个表加起来约100k个int约0.4MB内存消耗很小。但当n20时2^201,048,5761M*20 ≈ 20M个状态每个int4字节仅DP表就需要约80MB加上前驱表就超过160MB这可能超出一些在线判题系统的内存限制。因此空间也是限制n不能太大的一个重要因素。4.3 潜在优化方向尽管状态压缩DP已经是解决此类排列优化问题的标准且高效的方法但在面对极限数据时我们还可以考虑一些优化剪枝与启发式在DP转移前可以对字符串进行排序或使用启发式规则如长度、公共前缀等来优先处理更可能产生大重叠的转移虽然不能改变最坏复杂度但可能提升平均速度。记忆化搜索DFSMemoization有时用递归记忆化的方式实现DP代码可能更清晰并且可以结合深度优先搜索的特性配合上下界剪枝例如当前长度加上剩余字符串的最小可能增长长度如果已经超过已知最优解则剪枝这在某些情况下比递推更快。迭代加深或分支定界对于更大的n精确算法可能不再适用。可以考虑使用近似算法如迭代局部搜索、模拟退火或遗传算法来寻找一个接近最优的解。题目如果只要求近似解这是一个方向。使用更紧凑的状态表示如果只求最短长度而不需要构造路径parent数组可以省略。此外有些实现使用dp[mask]只记录到达该mask的最短长度而用另一个数组last[mask]记录最后一个字符串但这样在回溯构造路径时会麻烦一些。使用整数运算优化判断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[1i][i] words[i].size()必须正确设置。确保1 i在整数范围内i 32对于32位int。空输入或单字符串输入这是常见的边界情况。如果预处理后n0所有字符串都是其他字符串的子串按照题目要求通常返回任意一个原字符串即可。如果n1直接返回该字符串。代码开头就要处理这些情况。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中自然也不会发生ij的转移。前驱记录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])。这里要注意当ij时find会返回0自己当然是自己的子串所以必须加上i ! j的条件。同时我们只当words[i].size() words[j].size()时才进行检查这是一个小优化。5.5 调试输出与可视化对于复杂的DP添加调试输出是理解程序运行过程、定位错误的好方法。可以在关键位置打印信息// 例如在状态转移后打印某个状态的变化 if (mask someSpecificMask i someSpecificI j someSpecificJ) { cout dp[ bitset4(mask) ][ i ] dp[mask][i] - dp[ bitset4(newMask) ][ j ] newLen endl; } // 或者在回溯完成后打印路径 cout Path: ; for (int idx : path) cout idx ; cout endl;对于小规模输入如n4你甚至可以打印出整个DP表观察其填充过程这能帮你验证状态定义和转移方程是否正确。最后多使用题目提供的示例和自编的小例子进行测试。从最简单的两个字符串开始[ab, bc]答案应为abc逐步增加复杂度确保每一步的输出都符合预期。