Java最长公共子序列|动态规划经典算法深度解析

java最长公共子序列(Longest Common Subsequence,简称LCS)是字符串处理与动态规划领域的核心问题之一。该问题不仅在算法竞赛(如LeetCode、Codeforces)中高频出现,更广泛应用于版本控制系统(如Git)、生物序列比对(如DNA比对)、文本差异分析等工程场景。本文将系统讲解其数学定义、经典动态规划解法、多种Java实现方式、性能优化路径、典型面试真题及延伸知识,帮助开发者从原理到实战全面掌握。

一、java最长公共子序列的严格数学定义

给定两个序列 X = 和 Y = ,若存在一个序列 Z = 同时满足:

  1. Z 是 X 的子序列:即存在严格递增的下标序列 i₁ < i₂ < ... < iₖ,使得 zₚ = x_{iₚ}(∀p∈[1,k])
  2. Z 是 Y 的子序列:即存在严格递增的下标序列 j₁ < j₂ < ... < jₖ,使得 zₚ = y_{jₚ}(∀p∈[1,k])

则称 Z 是 X 与 Y 的公共子序列。在所有公共子序列中,长度最大的称为最长公共子序列(LCS)。注意:LCS不唯一,但长度唯一。

⚠️ 关键辨析:

该问题最早由Szymon Grabowski于1972年提出,1974年S. R. Kosaraju与R. E. Tarjan给出了O(mn)动态规划解法,成为算法教科书经典案例。

二、动态规划建模与状态转移详解

设 dp[i][j] 表示 X 的前 i 个字符(X[0..i-1])与 Y 的前 j 个字符(Y[0..j-1])的LCS长度。则状态转移方程如下:

当 i = 0 或 j = 0 时,dp[i][j] = 0(空串与任意串的LCS长度为0)

否则:

若 X[i-1] == Y[j-1],则 dp[i][j] = dp[i-1][j-1] + 1
否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])

该方程的直观解释:

✅ 举例推演(X="ABCBDAB", Y="BDCABA"):

i\j0BDCABA
00000000
A0000111
B0111122
C0112222
B0112233
D0122233
A0122334
B0122344

最终 dp[7][6] = 4,即LCS长度为4。

💡 时间复杂度:O(mn),空间复杂度:O(mn)。其中 m = len(X), n = len(Y)。

三、Java语言多版本实现与代码规范性分析

3.1 基础二维DP实现(推荐教学与调试)

public class LCSBasic {
    public static int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = s2.charAt(j - 1);
                if (c1 == c2) {
                    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];
    }
}

3.2 空间优化版:滚动数组(O(n)空间)

由于 dp[i][j] 仅依赖上一行(i-1)和当前行左侧值,可用两行滚动数组替代二维表:

public class LCSOptimized {
    public static int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (n == 0) return 0;
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = s2.charAt(j - 1);
                if (c1 == c2) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            // 交换引用,避免数组拷贝
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        return prev[n];
    }
}

⚠️ 注意:此版本仅返回长度,无法恢复具体LCS序列。若需路径,需回溯或使用其他结构。

3.3 支持路径恢复的完整实现

在dp表构建完成后,从右下角反向回溯:

public class LCSWithPath {
    public static String lcsPath(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 构建dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(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字符串
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.append(s1.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.reverse().toString();
    }
    // 测试用例
    public static void main(String[] args) {
        String s1 = "ABCBDAB", s2 = "BDCABA";
        System.out.println("LCS长度: " + lcsLength(s1, s2)); // 4
        System.out.println("LCS路径: " + lcsPath(s1, s2));   // "BDAB" 或其他合法LCS
    }
}

四、性能优化进阶:从O(mn)到Hirschberg算法

4.1 空间复杂度对比表

算法时间复杂度空间复杂度是否支持路径恢复
标准DPO(mn)O(mn)✅ 是
滚动数组O(mn)O(min(m,n))❌ 否(仅长度)
HirschbergO(mn)O(min(m,n))✅ 是(分治+递归)
Myers算法O(ND)O(N+D²)✅ 是(编辑距离视角)

其中 D = 编辑距离;Hirschberg算法基于分治策略:将问题拆分为左右两半,递归求解左半段的LCS路径,再递归右半段,总空间仍为O(n),但实现复杂度高,常用于生物信息学。

4.2 特殊优化场景

  • 当两字符串字符集小(如DNA序列仅A/T/C/G),可用位运算加速:将字符映射为位掩码,利用位并行技术(Bitap)将时间降至O(mn/word_size),典型如Sun的LCS实现。
  • 当 m 或 n 很小(如≤128),可用int数组位压缩:每32位存一个字符状态,用位与(&)操作快速判断字符匹配。
  • 当仅需长度且 m,n 很大,可用Hirschberg + 滚动数组组合:递归深度为O(log n),每层空间O(n),总空间O(n log n),但实际中常近似O(n)。

五、LeetCode真题与面试高频考点解析

LeetCode 1143
LeetCode 583
LeetCode 1035

5.1 LeetCode 1143. 最长公共子序列

题目描述:给定两个字符串 text1 和 text2,返回它们的最长公共子序列的长度。若不存在公共子序列,返回0。

示例:输入 text1="abcde", text2="ace" → 输出 3(LCS="ace")

✅ 官方题解即标准DP,但需注意边界处理。常见错误:

  • 索引越界:dp[i][j] 对应 s1[i-1] 和 s2[j-1],初始化dp[0][*] = dp[*][0] = 0
  • 未使用char数组缓存:重复调用charAt()可能影响性能,尤其在大数据集时。

推荐提交代码(Java):

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                if (c == text2.charAt(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];
    }
}

⏱️ 提交结果(2024年数据):耗时2ms(超过99%),内存41.2MB(超过86%)

5.2 LeetCode 583. 两个字符串的删除操作

题目:给定两个单词 word1 和 word2,返回使得 word1 和 word2 相同所需的最小步数。每步可删除任意一个字符串中的一个字符。

💡 等价转化:删除字符数 = len1 + len2 - 2 × LCS长度

示例:word1="sea", word2="eat" → LCS="ea"(长度2)→ 步数=3+3-4=2

class Solution {
    public int minDistance(String word1, String word2) {
        int lcsLen = lcs(word1, word2);
        return word1.length() + word2.length() - 2 * lcsLen;
    }
    private int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(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];
    }
}

5.3 LeetCode 1035. 不相交的线

题目:在两条独立的水平线上写数字,A[i] 与 B[j] 之间可连线当且仅当 A[i] == B[j] 且连线不相交。求最多可画多少条线。

💡 本质就是LCS:不相交 ⇨ 保持顺序 ⇨ 子序列定义!

因此直接调用LCS函数即可,无需额外处理。

📌 面试官常追问:若要求输出具体连线方案(如A[0]连B[2]),如何设计?

答:在回溯时记录路径坐标对 (i,j),需维护List,注意去重与排序。