Java版LeetCode热题100之最长公共子序列：从原理到实战的深度解析
摘要：本文全面剖析 LeetCode 热题 100 中的经典动态规划问题——「最长公共子序列（LCS）」。我们将从原题回顾出发，系统讲解动态规划设计、代码实现、复杂度分析，并延伸至空间优化、面试应对、实际应用场景等多个维度。全文结构严谨、内容翔实，适合算法进阶与面试准备。
一、原题回顾
题目描述：
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。
子序列定义：由原字符串在不改变字符相对顺序的情况下删除某些字符（也可以不删除）后组成的新字符串。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3。示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3。示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0。约束条件：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成
本题是动态规划领域的标志性问题，广泛应用于文本比较、生物信息学、版本控制等领域。它不仅是面试高频题，更是理解 DP 思想的绝佳范例。
二、原题分析
2.1 问题本质
在两个字符串中，找出一个最长的公共子序列（注意：不是子串！）。关键区别：
| 概念 | 是否连续 | 示例 |
|---|---|---|
| 子串（Substring） | 是 | "ab"是"abc"的子串 |
| 子序列（Subsequence） | 否 | "ac"是"abc"的子序列 |
因此，LCS 允许“跳跃”匹配，只要保持字符顺序一致即可。
2.2 为什么不能用贪心？
直觉上，我们可能想“从左到右，遇到相同字符就匹配”。但这是错误的！
反例：
text1 = "abcde"text2 = "ace"
若贪心匹配'a'后立即匹配'c'，会错过更优解？其实这里贪心是对的。
再看更强反例：
text1 = "abcbdab"text2 = "bdcaba"
贪心可能先匹配第一个'b'，但最优解包含后面的'b'。实际上，LCS 不具备贪心选择性质，必须考虑所有可能性。
2.3 动态规划的适用性
LCS 具备 DP 的两大核心特征：
最优子结构：
若text1[i-1] == text2[j-1]，则 LCS 长度 =LCS(text1[0:i-1], text2[0:j-1]) + 1
否则，LCS 长度 =max(LCS(text1[0:i-1], text2), LCS(text1, text2[0:j-1]))重叠子问题：
多次计算相同的子串对的 LCS，如("ab", "a")可能被多次调用。
因此，DP 是理想解法。
三、答案构思：动态规划设计
3.1 状态定义
设dp[i][j]表示text1的前i个字符 与text2的前j个字符 的最长公共子序列长度。
注意：这里
i和j是长度，不是索引。因此text1[0:i]对应索引0到i-1。
我们的目标是求dp[m][n]，其中m = text1.length(),n = text2.length()。
3.2 边界条件
- 当
i = 0（text1为空）：dp[0][j] = 0（对任意j） - 当
j = 0（text2为空）：dp[i][0] = 0（对任意i）
即：空字符串与任何字符串的 LCS 长度为 0。
3.3 状态转移方程
对于i > 0且j > 0：
情况1：
text1[i-1] == text2[j-1]
两个字符相同，可加入 LCS：
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1] + 1dp[i][j]=dp[i−1][j−1]+1情况2：
text1[i-1] != text2[j-1]
两个字符不同，取两种跳过方式的最大值：
d p [ i ] [ j ] = max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = \max(dp[i-1][j], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])
3.4 计算顺序
由于dp[i][j]依赖于dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]，我们按行优先顺序遍历（i从 1 到 m，j从 1 到 n），确保依赖项已计算。
四、完整答案（Java 实现）
4.1 基础动态规划解法
classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intm=text1.length();intn=text2.length();// 创建 (m+1) x (n+1) 的 dp 表int[][]dp=newint[m+1][n+1];// 填充 dp 表for(inti=1;i<=m;i++){charc1=text1.charAt(i-1);for(intj=1;j<=n;j++){charc2=text2.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]);}}}returndp[m][n];}}4.2 空间优化版（滚动数组）
classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intm=text1.length();intn=text2.length();// 只需两行：prev 和 currint[]prev=newint[n+1];int[]curr=newint[n+1];for(inti=1;i<=m;i++){charc1=text1.charAt(i-1);for(intj=1;j<=n;j++){charc2=text2.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;}returnprev[n];}}4.3 进一步优化：单数组版
classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intm=text1.length();intn=text2.length();// 确保 text2 是较短的字符串，减少空间if(m<n){returnlongestCommonSubsequence(text2,text1);}int[]dp=newint[n+1];for(inti=1;i<=m;i++){intprevDiag=0;// 保存 dp[i-1][j-1]charc1=text1.charAt(i-1);for(intj=1;j<=n;j++){inttemp=dp[j];// 保存当前 dp[j]（即 dp[i-1][j]）charc2=text2.charAt(j-1);if(c1==c2){dp[j]=prevDiag+1;}else{dp[j]=Math.max(dp[j],dp[j-1]);}prevDiag=temp;// 更新为下一轮的 dp[i-1][j-1]}}returndp[n];}}五、代码分析
5.1 基础 DP 版
- 清晰直观：直接对应状态转移方程。
- 易于调试：可打印
dp表验证过程。 - 示例验证（
text1="abcde",text2="ace"）：
构建dp表如下（只展示非零部分）：
| a | c | e | ||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
最终dp[5][3] = 3，正确。
5.2 滚动数组版
- 空间优化：从O ( m n ) O(mn)O(mn)降至O ( n ) O(n)O(n)。
- 逻辑等价：
prev相当于上一行，curr是当前行。 - 注意：内层循环仍需从左到右，因为
curr[j]依赖curr[j-1]。
5.3 单数组版
- 极致优化：仅用一个数组 + 一个变量
prevDiag。 - 关键技巧：在覆盖
dp[j]前，用temp保存旧值，供下一轮作为prevDiag。 - 推荐：在空间敏感场景使用。
六、时间复杂度与空间复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 基础 DP | O ( m n ) O(mn)O(mn) | O ( m n ) O(mn)O(mn) | 标准解法 |
| 滚动数组 | O ( m n ) O(mn)O(mn) | O ( n ) O(n)O(n) | 优化空间 |
| 单数组 | O ( m n ) O(mn)O(mn) | O ( min ( m , n ) ) O(\min(m, n))O(min(m,n)) | 最优空间 |
注：时间复杂度无法进一步优化，因为必须比较每对字符。空间优化基于“当前行只依赖上一行”的性质。
七、问题解答（FAQ）
Q1：为什么dp数组要开(m+1) x (n+1)，而不是m x n？
答：为了方便处理边界条件。
dp[0][j]和dp[i][0]直接表示空字符串的情况，无需特殊判断。若用m x n，需额外处理i=0或j=0的情况，代码更复杂。
Q2：能否返回具体的 LCS 字符串，而不仅是长度？
答：可以！需在 DP 过程中记录“选择路径”，然后从
dp[m][n]回溯：StringBuilderlcs=newStringBuilder();inti=m,j=n;while(i>0&&j>0){if(text1.charAt(i-1)==text2.charAt(j-1)){lcs.append(text1.charAt(i-1));i--;j--;}elseif(dp[i-1][j]>dp[i][j-1]){i--;}else{j--;}}returnlcs.reverse().toString();
Q3：如果字符串很长（如10 5 10^5105），怎么办？
答：标准 DP 会超内存（10 10 10^{10}1010空间）。此时需：
- Hirschberg 算法：空间O ( min ( m , n ) ) O(\min(m,n))O(min(m,n))，时间O ( m n ) O(mn)O(mn)，可输出 LCS。
- 近似算法：如基于后缀数组的方法，但通常不要求。
Q4：LCS 和编辑距离有什么关系？
答：密切相关！编辑距离（插入、删除、替换）可通过 LCS 计算：
EditDistance = m + n − 2 × LCS \text{EditDistance} = m + n - 2 \times \text{LCS}EditDistance=m+n−2×LCS
（假设只允许插入和删除操作）
八、优化思路
8.1 空间优化（已实现）
- 滚动数组：利用 DP 的局部依赖性。
- 单数组 + 对角线变量：进一步压缩空间。
8.2 时间优化（理论）
- 四 Russians 算法：将时间降至O ( m n / log n ) O(mn / \log n)O(mn/logn)，但实现复杂。
- 位并行算法：适用于小字符集（如 DNA 序列），用位运算加速。
8.3 工程优化
- 提前终止：若某行全为 0，后续行也必为 0（但最坏情况不变）。
- 缓存友好：确保内层循环访问连续内存（Java 数组行优先，已满足）。
九、数据结构与算法基础知识点回顾
9.1 动态规划核心思想
- 分治 + 记忆化：将问题分解为子问题，存储子问题解避免重复计算。
- 自底向上：从小规模问题开始，逐步构建大规模解。
9.2 二维 DP 的通用模式
- 定义
dp[i][j]表示前i个 A 和前j个 B 的某种最优值。 - 初始化边界（通常
i=0或j=0）。 - 写出状态转移方程（分情况讨论）。
- 确定遍历顺序（确保依赖项已计算）。
9.3 子序列 vs 子串
| 特性 | 子序列 | 子串 |
|---|---|---|
| 连续性 | 否 | 是 |
| DP 状态 | dp[i][j] | dp[i][j]（但转移不同） |
| 典型问题 | LCS, LIS | 最长公共子串, KMP |
9.4 空间优化技巧
- 滚动数组：当状态只依赖前 k 行/列时，用 k 个一维数组替代二维。
- 状态压缩：用位运算或数学变换减少状态表示（如背包问题）。
十、面试官提问环节（模拟）
Q1：你能手写 LCS 的 DP 解法吗？
答：（现场写出基础 DP 代码，并解释状态定义和转移方程）
Q2：如何优化空间复杂度？
答：观察到
dp[i][j]只依赖上一行和当前行左侧，可用滚动数组将空间从O ( m n ) O(mn)O(mn)降至O ( n ) O(n)O(n)。进一步，用单数组加对角线变量，可降至O ( min ( m , n ) ) O(\min(m,n))O(min(m,n))。
Q3：如果要求输出所有 LCS，怎么办？
答：回溯时需考虑所有可能路径。当
dp[i-1][j] == dp[i][j-1]时，两条路径都可能产生 LCS，需用 DFS 枚举所有分支。注意去重（可能有重复 LCS）。
Q4：LCS 在 Git diff 中是如何应用的？
答：Git 的 diff 算法基于 LCS。将两版本文件视为字符串，LCS 对应“未修改的行”，其余行为“增删改”。通过 LCS 可高效生成差异补丁。
十一、这道算法题在实际开发中的应用
LCS 不仅是面试题，更是许多实际系统的基石：
11.1 版本控制系统（如 Git）
- diff 算法：比较两个文件的差异，核心就是 LCS。
- 合并冲突检测：通过 LCS 判断哪些行被双方修改。
11.2 生物信息学
- DNA/蛋白质序列比对：寻找基因序列的相似区域，用于进化分析、疾病研究。
- 工具如 BLAST 就基于 LCS 的变种。
11.3 文本处理
- 抄袭检测：比较两篇文章的 LCS 长度，判断相似度。
- 自动摘要：提取与原文 LCS 最长的句子作为摘要。
11.4 数据同步
- 增量同步：客户端和服务端通过 LCS 找出差异部分，只传输变化数据。
- 如 Dropbox、Google Drive 的文件同步机制。
启示：LCS 是连接理论算法与工程实践的桥梁。
十二、相关题目推荐
掌握 LCS 后，可挑战以下进阶题：
| 题目 | 链接 | 难度 | 关键变化 |
|---|---|---|---|
| 1143. 最长公共子序列 | LeetCode | 中等 | 本题 |
| 1092. 最短公共超序列 | LeetCode | 困难 | 输出包含两字符串的最短字符串 |
| 718. 最长重复子数组 | LeetCode | 中等 | 子串（连续）而非子序列 |
| 583. 两个字符串的删除操作 | LeetCode | 中等 | 求最少删除次数使两串相等（= m+n-2*LCS） |
| 1035. 不相交的线 | LeetCode | 中等 | 本质是 LCS（连线不交叉 ⇨ 保持顺序） |
学习建议：先彻底掌握 LCS → 尝试 583（直接应用）→ 挑战 1092（需构造字符串）→ 对比 718（连续 vs 非连续）。
十三、总结与延伸
13.1 核心收获
- DP 建模能力：学会定义状态、写出转移方程、处理边界。
- 空间优化意识：理解滚动数组的原理与应用场景。
- 问题抽象能力：将实际问题（如 diff）转化为 LCS 模型。
13.2 延伸思考
- 多字符串 LCS：3 个或更多字符串的 LCS？→ NP-hard，需启发式算法。
- 带权重的 LCS：不同字符匹配有不同收益？→ 修改转移方程。
- 流式 LCS：字符串以流形式输入？→ 需在线算法（如基于后缀自动机）。
13.3 学习建议
- 动手实现：至少手写基础 DP 和空间优化版。
- 画图辅助：用
"abcde"和"ace"模拟 DP 表填充过程。 - 举一反三：思考“如果要求子串而非子序列，怎么改？”
结语：最长公共子序列是一道“经典永流传”的算法题。它像一把钥匙，打开了动态规划、字符串处理、实际应用的大门。掌握它，你不仅能在面试中游刃有余，更能理解背后深刻的计算机科学思想。
欢迎点赞、收藏、评论交流！
关注我，获取更多 LeetCode 热题深度解析！
字数统计：约 9300 字（含代码与公式）
适用读者：LeetCode 刷题者、校招/社招面试准备者、算法爱好者
