algorithms►leetcode

018-最长公共子序列(DP)

最长公共子序列 LCS

问题描述

给定两个字符串，找出它们的最长公共子序列的长度。子序列不需要连续。

示例：

1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，长度为3

动态规划解法

解题思路

  1. 创建二维dp数组，dp[i][j]表示text1[0..i-1]和text2[0..j-1]的LCS长度
  2. 初始化：空字符串的LCS为0
  3. 状态转移：
    • 当text1[i-1] == text2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1
    • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  4. 最终结果：dp[m][n]（m和n分别是两个字符串的长度）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let 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] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[m][n];
}

复杂度分析

  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

空间优化解法

可以将空间复杂度优化到O(min(m,n))：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function longestCommonSubsequence(text1, text2) {
    if (text1.length < text2.length) {
        [text1, text2] = [text2, text1]; // 确保text2是较短的
    }
    
    const m = text1.length, n = text2.length;
    let prev = new Array(n+1).fill(0);
    let curr = new Array(n+1).fill(0);
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i-1] === text2[j-1]) {
                curr[j] = prev[j-1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j-1]);
            }
        }
        [prev, curr] = [curr, prev]; // 交换引用
    }
    
    return prev[n];
}

重建LCS序列

如果需要返回具体的LCS序列而不仅仅是长度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function getLCS(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
    
    // 填充dp表
    for (let i = 1; i <= m; i++) {
        for (let 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] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // 回溯重建LCS
    let i = m, j = n;
    const lcs = [];
    while (i > 0 && j > 0) {
        if (text1[i-1] === text2[j-1]) {
            lcs.unshift(text1[i-1]);
            i--;
            j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return lcs.join('');
}

示例测试

1
2
3
console.log(longestCommonSubsequence("abcde", "ace")); // 3
console.log(longestCommonSubsequence("abc", "def")); // 0
console.log(getLCS("abcde", "ace")); // "ace"

算法图解

以text1=”abcde”和text2=”ace”为例：

  1. 初始化dp表（(m+1)×(n+1)的零矩阵）

  2. 填充dp表：

    • 当字符匹配时，取左上角值+1
    • 否则取上方或左方的最大值

  3. 最终dp表右下角的值即为LCS长度

    a c e
    a 1 1 1
    b 1 1 1
    c 1 2 2
    d 1 2 2
    e 1 2 3

总结

最长公共子序列问题通过动态规划可以高效解决：

  1. 定义dp数组表示子问题解
  2. 找出状态转移方程
  3. 填充dp表
  4. 从dp表获取结果

空间优化版本适合处理大字符串，而重建序列版本可以获取具体的LCS字符串。