面试必问 lcs算法源码解析：3步讲透最长公共子序列

上周陪朋友面某二线大厂后端开发，面试官刚抛出“请手写最长公共子序列”这道题，他脑子直接宕机。更惨的是，他在 LeetCode 上跑测试用例时，满屏的 IndexOutOfBoundsException 和 NullPointerException，StackTrace 长得像天书，根本看不出哪里越界。这种场景太常见了：背了模板，代码能写出来，但一遇到边界条件或者空间优化，直接翻车。今天我们就从源码解析的角度，把 LCS（Longest Common Subsequence）算法彻底拆解。这不是为了让你死记硬背，而是让你看懂它背后的状态转移逻辑，下次再看到报错，你能秒定位问题，而不是对着 StackTrace 发呆。

考点梳理：为什么大厂爱考 LCS

在面试中，LCS 是动态规划（DP）领域的“守门员”。它不像背包问题那样有变种，也不像编辑距离那样复杂，但它考察的核心能力非常纯粹：二维状态数组的构建、状态转移方程的推导以及空间优化。

很多候选人栽跟头，不是因为不会写 DP，而是对“子序列”和“子串”的概念混淆。子序列不要求连续，只要顺序一致即可。比如 "ABC" 是 "AXBCY" 的子序列，但不是子串。这个概念混淆会导致状态转移方程写错。

另一个高频考点是回溯路径。面试官很少只让你返回长度，通常会追问：“如何还原出那个具体的子序列？”这就涉及到从 DP 表格的右下角往回推，利用 dp[i][j] 的值判断当前匹配字符是否属于最长子序列的一部分。

根据 Stack Overflow 上关于 Dynamic Programming 的高赞回答，LCS 问题的时间复杂度下界是 \(O(mn)\)，空间复杂度可以优化到 \(O(\min(m, n))\)。如果你的代码跑不出这个复杂度，说明你在用暴力递归或者没做滚动数组优化，这在性能敏感的业务场景中是不可接受的。

标准答法：面试时的沟通策略

拿到这道题，不要急着敲代码。先花 30 秒确认边界：两个字符串长度是否为零？如果为空，直接返回 0。这一步能展示你的严谨性。

接着，用大白话解释思路：“我打算用一个二维数组 dp，dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度。”

然后推导状态转移方程，这是得分点：

如果 s1[i-1] == s2[j-1]，说明这两个字符匹配，那么 dp[i][j] = dp[i-1][j-1] + 1。
如果不匹配，那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。意思是，要么丢弃 s1 的最后一个字符，要么丢弃 s2 的最后一个字符，取两者中较长的公共子序列。

最后，主动提及空间优化：“如果只关心长度，可以用两个一维数组滚动更新，空间复杂度降为 \(O(n)\)。如果需要还原路径，必须保留完整的二维数组或者记录决策树。”

这种“先定义状态，再推导方程，最后谈优化”的结构，是面试官最想听到的逻辑闭环。它证明你不是在背题，而是真的理解了 DP 的本质。

代码实现：逐行拆解与避坑

下面给出 Java 标准实现，包含长度计算和路径回溯。注意看注释里的细节，这些往往是 StackTrace 报错的重灾区。

public class LCSSolver {/*** 计算最长公共子序列的长度* @param s1 字符串1* @param s2 字符串2* @return LCS 长度*/public int lengthOfLCS(String s1, String s2) {if (s1 == null || s2 == null) {return 0;}int m = s1.length();int n = s2.length();// 初始化 dp 数组，多开一行一列，处理边界情况// dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度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];}/*** 回溯得到具体的 LCS 字符串* @param s1 字符串1* @param s2 字符串2* @return LCS 字符串*/public String getLCS(String s1, String s2) {if (s1 == null || s2 == null) {return "";}int m = s1.length();int 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]);}}}// 第二步：回溯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]) {// 上一行的值更大，说明丢弃 s1 的当前字符i--;} else {// 左边一列的值更大（或相等），说明丢弃 s2 的当前字符j--;}}// 回溯得到的结果是逆序的，需要反转return sb.reverse().toString();}
}

关键点解析：

下标偏移：dp 数组开了 m+1 和 n+1，这样 dp[0][j] 和 dp[i][0] 天然为 0，无需特殊处理边界。如果你不开这一行，代码里就会满屏的 if (i==0) ...，极易出错。
回溯逻辑：注意 else if 分支。当 dp[i-1][j] 和 dp[i][j-1] 相等时，我们选择 j--（丢弃 s2 的字符）。其实选哪个都行，但必须一致，否则逻辑混乱。
字符串反转：StringBuilder 在回溯过程中是从后往前添加字符的，最后必须 reverse()。漏掉这一步，返回的字符串是倒的，测试用例直接挂掉。

追问与延伸：空间优化与变种

面试官吃完你的标准答案，通常会问：“如果字符串长度达到 \(10^6\)，你的二维数组会 OOM，怎么优化？”

这时，你拿出滚动数组方案。既然 dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]，我们只需要保留上一行的数据。

public int lengthOfLCSSpaceOptimized(String s1, String s2) {// 确保 n 是较短的字符串长度，进一步减少空间if (s1.length() < s2.length()) {String temp = s1;s1 = s2;s2 = temp;}int n = s2.length();int[] prev = new int[n + 1];int[] curr = new int[n + 1];for (int i = 1; i <= s1.length(); i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {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];
}

这里有个陷阱：不能直接 prev = curr，必须交换引用。否则 prev 和 curr 指向同一个对象，下一轮计算时数据会被覆盖，导致结果错误。这也是很多候选人调试半天找不到的 Bug 根源。

再进一步，如果面试官问：“如何找出所有的 LCS？”这就复杂了。你需要在回溯时，如果 dp[i-1][j] == dp[i][j-1]，说明有两条路径，需要分支搜索。这通常作为高级面试题，考察 DFS 和剪枝能力。