Leetcode最短超串DP实现：大向量内存分配错误求解

问题分析 #

你实现的最短超串DP解法在处理小规模序列时正常，但当序列数n≈50时，出现memory allocation of 27021597764222976 bytes failed错误，核心原因是状态规模爆炸：

• 原DP数组dp: Vec<Vec<String>>的维度是[2^n][n]，当n=50时，2^50是约1e15的天文数字，无论堆空间多大都不可能分配这么多内存，这是算法设计层面的问题，不是单纯加内存能解决的。

优化思路 #

原方案直接存储每个状态对应的完整超串，既浪费内存，也完全无法处理n≥20的场景。我们需要调整DP状态的存储方式：

1. 压缩DP状态：将dp[mask][j]从存储完整字符串，改为存储两个整数：
   • 最短超串的长度
   • 前驱节点（即构造该超串时，最后一步是从哪个节点k转移而来）
2. 预处理重叠长度：提前计算任意两个序列i和j的最大重叠长度（i的后缀与j的前缀的最长匹配），代替存储后缀字符串，减少内存占用的同时，后续拼接时可直接计算结果。

优化后的Rust实现 #

fn shortest_superstring(sequences: Vec<String>) -> String {
    let n = sequences.len();
    if n == 0 {
        return String::new();
    }

    // 预处理：计算i到j的最大重叠长度（i的后缀和j的前缀的最长匹配）
    let mut overlap = vec![vec![0; n]; n];
    for i in 0..n {
        for j in 0..n {
            if i == j {
                continue;
            }
            let s_i = &sequences[i];
            let s_j = &sequences[j];
            // 找最大的k，使得s_i的最后k个字符等于s_j的前k个字符
            let max_possible = s_i.len().min(s_j.len());
            for k in (0..=max_possible).rev() {
                if s_i.ends_with(&s_j[0..k]) {
                    overlap[i][j] = k;
                    break;
                }
            }
        }
    }

    // DP状态定义：
    // dp[mask][j] = (最短长度, 前驱节点)
    // mask是表示已选序列的位掩码，j是当前超串的结尾序列索引
    let mut dp = vec![vec![(usize::MAX, usize::MAX); n]; 1 << n];
    // 初始化：单个序列的情况
    for j in 0..n {
        dp[1 << j][j] = (sequences[j].len(), usize::MAX);
    }

    // 遍历所有掩码
    for mask in 1..(1 << n) {
        // 找出当前掩码包含的所有序列索引
        let indexes: Vec<usize> = (0..n).filter(|&j| (mask & (1 << j)) != 0).collect();
        for &j in &indexes {
            let prev_mask = mask & !(1 << j);
            if prev_mask == 0 {
                continue; // 单个序列的情况已经初始化过
            }
            // 尝试从所有可能的前驱k转移过来
            for &k in &indexes {
                if k == j || (prev_mask & (1 << k)) == 0 {
                    continue;
                }
                let prev_len = dp[prev_mask][k].0;
                if prev_len == usize::MAX {
                    continue;
                }
                let new_len = prev_len + sequences[j].len() - overlap[k][j];
                // 如果新长度更短，更新DP状态
                if new_len < dp[mask][j].0 {
                    dp[mask][j] = (new_len, k);
                }
            }
        }
    }

    // 找到所有序列都包含时的最短超串的结尾节点
    let full_mask = (1 << n) - 1;
    let (_, end_j) = dp[full_mask].iter().enumerate()
        .min_by_key(|&(_, &(len, _))| len)
        .unwrap();

    // 回溯构造最短超串
    let mut current_mask = full_mask;
    let mut current_j = end_j;
    let mut result_parts = Vec::new();

    while current_mask != 0 {
        result_parts.push(current_j);
        let (_, prev_k) = dp[current_mask][current_j];
        if prev_k == usize::MAX {
            break;
        }
        current_mask &= !(1 << current_j);
        current_j = prev_k;
    }

    // 反转得到构造顺序
    result_parts.reverse();
    let mut superstring = sequences[result_parts[0]].clone();
    for i in 1..result_parts.len() {
        let prev = result_parts[i-1];
        let curr = result_parts[i];
        let overlap_len = overlap[prev][curr];
        superstring.push_str(&sequences[curr][overlap_len..]);
    }

    superstring
}

优化效果说明 #

• 内存占用：原方案每个状态存储字符串，优化后每个状态仅存储两个整数，内存占用从O(2^n * n * L)（L是字符串平均长度）降至O(2^n * n)，即使n=20，2^20≈1e6，乘以20再乘以每个整数8字节，仅约160MB，完全可控。
• 注意：即使如此，当n≥30时，2^30≈1e9，内存占用会达到约16GB，仍然超出常规硬件，此时需要更高级的剪枝或近似算法；而n=50时，精确解法的时间复杂度O(n^2 * 2^n)本身已完全无法完成计算，只能考虑贪心、遗传算法等启发式方案。

内容的提问来源于stack exchange，提问作者jllPons