知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 最长公共子序列(LCS) ## 题目(LeetCode 1143) 给定两个字符串,返回它们的最长公共子序列的长度。 ``` 输入:text1="abcde", text2="ace" 输出:3("ace") ``` ## 先搞清楚:子序列 vs 子串 ``` 子串(Substring):必须连续 "abcde" 的子串:a, ab, abc, abcd, abcde, b, bc, ... 子序列(Subsequence):不要求连续,但要保持相对顺序 "abcde" 的子序列:a, b, c, ace, abce, abcde, ... "ace" 是 "abcde" 的子序列(a...c...e,顺序没变,中间可以跳) "ace" 不是 "abcde" 的子串(不连续) ``` ## 大白话理解 两个字符串从头开始比,当前字符相同就一起前进(公共长度+1),不同就试试跳过其中一个。 ``` text1 = "abcde" text2 = "ace" 比较 a 和 a:相同!公共长度 +1,两个都往后走 比较 b 和 c:不同,试试跳过 text1 的 b,或者跳过 text2 的 c,取最长的 比较 c 和 c:相同!公共长度 +1,两个都往后走 ... ``` ## 四步法 ``` 第 1 步:dp[i][j] = text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度 注意:前 i 个字符是 text1[0..i-1],用 1-indexed 方便处理边界 第 2 步: 如果 text1[i-1] == text2[j-1](当前字符相同): dp[i][j] = dp[i-1][j-1] + 1 含义:两个字符都选上,LCS 长度 = 去掉这两个字符后的 LCS + 1 如果 text1[i-1] != text2[j-1](当前字符不同): dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 含义:跳过 text1 的当前字符,或跳过 text2 的当前字符,取最长的 第 3 步:dp[0][j] = 0(text1 为空,LCS 为 0) dp[i][0] = 0(text2 为空,LCS 为 0) 第 4 步:从左到右,从上到下 ``` ### 为什么相同时取左上角 dp[i-1][j-1]? ``` text1[i-1] == text2[j-1],说明这两个字符可以同时加入 LCS 加入后,问题变成:text1 前 i-1 个字符和 text2 前 j-1 个字符的 LCS 这就是 dp[i-1][j-1],再 +1 就是答案 为什么不是 dp[i-1][j-1]+2? 因为我们只加入了一对相同的字符(text1[i-1] 和 text2[j-1]), 它们是同一个字符,只算一次 ``` ### 为什么不同时取 max(上方, 左方)? ``` 不同时,这两个字符不能同时加入 LCS 只能选择: 跳过 text1[i-1]:问题变成 text1 前 i-1 个 vs text2 前 j 个 → dp[i-1][j] 跳过 text2[j-1]:问题变成 text1 前 i 个 vs text2 前 j-1 个 → dp[i][j-1] 取两者最大值 ``` ## 手动模拟(这是理解的关键) ``` text1 = "abcde"(行) text2 = "ace"(列) 初始化(第 0 行和第 0 列全为 0): "" a c e "" [ 0 0 0 0 ] a [ 0 _ _ _ ] b [ 0 _ _ _ ] c [ 0 _ _ _ ] d [ 0 _ _ _ ] e [ 0 _ _ _ ] 逐格填写: dp[1][1]:text1[0]='a', text2[0]='a',相同! dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1 含义:text1="a" 和 text2="a" 的 LCS 是 "a",长度 1 dp[1][2]:text1[0]='a', text2[1]='c',不同 dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1 含义:text1="a" 和 text2="ac" 的 LCS 是 "a",长度 1 dp[1][3]:text1[0]='a', text2[2]='e',不同 dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 1) = 1 dp[2][1]:text1[1]='b', text2[0]='a',不同 dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1 dp[2][2]:text1[1]='b', text2[1]='c',不同 dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1 dp[2][3]:text1[1]='b', text2[2]='e',不同 dp[2][3] = max(dp[1][3], dp[2][2]) = max(1, 1) = 1 dp[3][1]:text1[2]='c', text2[0]='a',不同 dp[3][1] = max(dp[2][1], dp[3][0]) = max(1, 0) = 1 dp[3][2]:text1[2]='c', text2[1]='c',相同! dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2 含义:text1="abc" 和 text2="ac" 的 LCS 是 "ac",长度 2 dp[3][3]:text1[2]='c', text2[2]='e',不同 dp[3][3] = max(dp[2][3], dp[3][2]) = max(1, 2) = 2 dp[4][1]:text1[3]='d', text2[0]='a',不同 dp[4][1] = max(dp[3][1], dp[4][0]) = max(1, 0) = 1 dp[4][2]:text1[3]='d', text2[1]='c',不同 dp[4][2] = max(dp[3][2], dp[4][1]) = max(2, 1) = 2 dp[4][3]:text1[3]='d', text2[2]='e',不同 dp[4][3] = max(dp[3][3], dp[4][2]) = max(2, 2) = 2 dp[5][1]:text1[4]='e', text2[0]='a',不同 dp[5][1] = max(dp[4][1], dp[5][0]) = max(1, 0) = 1 dp[5][2]:text1[4]='e', text2[1]='c',不同 dp[5][2] = max(dp[4][2], dp[5][1]) = max(2, 1) = 2 dp[5][3]:text1[4]='e', text2[2]='e',相同! dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3 含义:text1="abcde" 和 text2="ace" 的 LCS 是 "ace",长度 3 最终 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 ✓ ``` ## 代码 ```java 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++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == 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]; } ``` 时间 O(m×n),空间 O(m×n)。 ## 如何还原实际的 LCS? ```java // 从右下角回溯 StringBuilder lcs = new StringBuilder(); int i = m, j = n; while (i > 0 && j > 0) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { lcs.append(text1.charAt(i - 1)); // 这个字符在 LCS 中 i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; // 来自上方,跳过 text1[i-1] } else { j--; // 来自左方,跳过 text2[j-1] } } return lcs.reverse().toString(); // 反转(因为是从后往前加的) ``` ## 一句话总结 相同就取左上角 +1,不同就取上方和左方的最大值。答案在右下角。 --- 上一篇:[05 - 零钱兑换](./05-coin-change.md) | 下一篇:[07 - 编辑距离](./07-edit-distance.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入