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

面试必问 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 和剪枝能力。 记忆口诀与实战建议 为了方便记忆，我总结了一个口诀：“建表多开行，匹配加一值，不匹配取大，回溯看对角。”建表多开行：dp 数组维度加 1，规避边界判断。 匹配加一值：字符相等，dp[i][j] = dp[i-1][j-1] + 1。 不匹配取大：字符不等，dp[i][j] = max(上, 左)。 回溯看对角：还原路径时，从右下角往左上角推，匹配则走对角线，不匹配走较大值方向。在准备面试时，建议你用 Python 快速实现一遍，验证逻辑；再用 Java 或 C++ 实现一遍，体会内存管理的细节。Python 的切片操作虽然方便，但掩盖了索引计算的底层逻辑，而 Java 的显式下标计算能让你更清晰地理解 i-1 和 j-1 的含义。 另外，不要忽视单元测试。自己构造几个极端用例：两个空字符串。 两个完全相同的字符串。 两个完全不相交的字符串。 一个字符串是另一个的子串。跑通这些用例，你的代码才算真正健壮。很多 StackTrace 错误，都是在这些极端边界条件下暴露出来的。 最后，LCS 算法虽然基础，但它是理解 DP 状态的基石。掌握了它，你再去看 LIS（最长递增子序列）、编辑距离、区间 DP，都会发现它们是 LCS 的变种或延伸。 你在准备动态规划面试时，还卡在哪个具体的状态推导上？或者遇到过什么诡异的越界报错？还有什么不懂的？评论区留言挨个回。