LeetCode 1143题超时求助：最长公共子序列代码仅过42/45用例

问题分析 #

你的代码超时核心原因有两点：

• 字符串值传递的冗余开销：solve函数中text1和text2按值传递，每次递归都会复制整个字符串，长字符串场景下这个开销会被急剧放大，直接拖慢执行速度。
• 递归栈的额外耗时：针对长度接近1000的字符串，递归深度可达近1000，栈调用的累积耗时会触发超时。

修复方案1：优化递归版本（最小改动） #

仅需将函数参数中的字符串改为const引用传递，避免每次递归复制字符串，即可大幅降低耗时，通过所有测试用例：

// solve(i,j)-->represents length of LCS till index i and j in string text1 and text2 respectively.
int solve(const string& text1, const string& text2, int i, int j, int dp[1001][1001]){
    // base case
    if(i < 0 || j < 0){
         return 0 ;
    }

    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    else{
        if(text1[i] == text2[j]){
            return dp[i][j] = 1 + solve(text1, text2, i-1, j-1, dp) ;                                
        }
    
        else{
            return dp[i][j] = max(solve(text1, text2, i, j-1, dp), solve(text1, text2, i-1, j, dp));
        }
     }
}

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    
    int dp[1001][1001];
    memset(dp, -1, sizeof(dp));
    
    return solve(text1, text2, m-1, n-1, dp);
}

修复方案2：迭代式动态规划（更稳定高效） #

如果想要彻底消除递归栈的开销，可以改用迭代方式填充DP表，性能更稳定，代码逻辑也更直观：

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    
    // dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

这个版本还可以进一步优化空间复杂度（比如用一维数组替代二维数组），但当前实现已经足够通过所有测试用例。

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