题目描述给定两个字符串 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 1000解题思路总览方法核心思想时间复杂度空间复杂度备注暴力搜索枚举所有子序列O(2^(nm))O(nm)会超时记忆化搜索递归 备忘录O(n*m)O(n*m)剪枝优化动态规划二维 dp 填表O(n*m)O(n*m)最常用空间优化一维数组滚动O(n*m)O(min(n,m))面试优化一、动态规划最常用核心思想定义dp[i][j] text1[0…i-1] 和 text2[0…j-1] 的最长公共子序列长度。状态转移方程如果 text1[i-1] text2[j-1] dp[i][j] dp[i-1][j-1] 1 // 两个字符匹配加入公共子序列 否则 dp[i][j] max(dp[i-1][j], dp[i][j-1]) // 两个字符不匹配丢弃其中一个图解text1 abcde, text2 ace 构建 dp 表n1 x m10行0列为空字符串的情况 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 即为答案代码实现classSolution{public:intlongestCommonSubsequence(string text1,string text2){intntext1.size(),mtext2.size();// dp[i][j] text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度vectorvectorintdp(n1,vectorint(m1,0));for(inti1;in;i){for(intj1;jm;j){if(text1[i-1]text2[j-1]){// 当前字符匹配LCS 长度 1dp[i][j]dp[i-1][j-1]1;}else{// 当前字符不匹配取两种情况的最大值dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}}returndp[n][m];}};二、算法流程图详细填表过程以 text1 abcde, text2 ace 为例 初始化dp[0][*] 0空字符串与任何字符串的 LCS 都是 0 dp[*][0] 0同样 填表顺序从左到右从上到下 Step 1: i1, text1[0]a j1, text2[0]a: a a - dp[1][1] dp[0][0] 1 1 j2, text2[1]c: a ! c - dp[1][2] max(dp[0][2], dp[1][1]) max(0, 1) 1 j3, text2[2]e: a ! e - dp[1][3] max(dp[0][3], dp[1][2]) max(0, 1) 1 Step 2: i2, text1[1]b j1, text2[0]a: b ! a - dp[2][1] max(dp[1][1], dp[2][0]) max(1, 0) 1 j2, text2[1]c: b ! c - dp[2][2] max(dp[1][2], dp[2][1]) max(1, 1) 1 j3, text2[2]e: b ! e - dp[2][3] max(dp[1][3], dp[2][2]) max(1, 1) 1 Step 3: i3, text1[2]c j1, text2[0]a: c ! a - dp[3][1] max(dp[2][1], dp[3][0]) max(1, 0) 1 j2, text2[1]c: c c - dp[3][2] dp[2][1] 1 1 1 2 j3, text2[2]e: c ! e - dp[3][3] max(dp[2][3], dp[3][2]) max(1, 2) 2 Step 4: i4, text1[3]d j1, text2[0]a: d ! a - dp[4][1] max(dp[3][1], dp[4][0]) max(1, 0) 1 j2, text2[1]c: d ! c - dp[4][2] max(dp[3][2], dp[4][1]) max(2, 1) 2 j3, text2[2]e: d ! e - dp[4][3] max(dp[3][3], dp[4][2]) max(2, 2) 2 Step 5: i5, text1[4]e j1, text2[0]a: e ! a - dp[5][1] max(dp[4][1], dp[5][0]) max(1, 0) 1 j2, text2[1]c: e ! c - dp[5][2] max(dp[4][2], dp[5][1]) max(2, 1) 2 j3, text2[2]e: e e - dp[5][3] dp[4][2] 1 2 1 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三、逐行解析对照原题代码intlongestCommonSubsequence(string text1,string text2){intntext1.size(),mtext2.size();// dp 大小为 (n1) x (m1)多一行一列用于处理空字符串// dp[i][j] text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度vectorvectorintdp(n1,vectorint(m1,0));// 从 1 开始遍历因为 dp[0][*] 和 dp[*][0] 已初始化为 0for(inti1;in;i){for(intj1;jm;j){if(text1[i-1]text2[j-1]){// 当前字符匹配来自左上角 1dp[i][j]dp[i-1][j-1]1;}else{// 当前字符不匹配取上方或左方的最大值dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}}returndp[n][m];}关键点解释语句含义dp(n 1, vectorint(m 1, 0))多一行一列第0行第0列表示空字符串的情况text1[i - 1] text2[j - 1]因为 dp 从 1 开始所以字符串索引要 -1dp[i][j] dp[i-1][j-1] 1两个字符匹配继承左上角结果 1dp[i][j] max(dp[i-1][j], dp[i][j-1])两个字符不匹配丢弃 text1 或 text2 的最后一个字符为什么 dp 数组是 (n1) x (m1)dp[i][j] 定义为 text1[0..i-1] 和 text2[0..j-1] 的 LCS - dp[0][j] 表示 text1 为空text2[0..j-1] 的 LCS 0 - dp[i][0] 表示 text2 为空text1[0..i-1] 的 LCS 0 - dp[n][m] 就是最终答案 这样设计的好处 - 不需要特殊处理边界 - 状态转移更统一四、空间优化面试加分思路观察 DP 表可以发现第 i 行只依赖第 i-1 行和第 i 行本身。所以可以用一维数组。classSolution{public:intlongestCommonSubsequence(string text1,string text2){intntext1.size(),mtext2.size();// 确保 text2 是较短的那个优化空间if(nm){swap(text1,text2);swap(n,m);}vectorintdp(m1,0);for(inti1;in;i){intprev0;// dp[i-1][j-1]即左上角的值for(intj1;jm;j){inttempdp[j];// 保存 dp[i][j]当前行第j列下一轮会用到if(text1[i-1]text2[j-1]){dp[j]prev1;}else{dp[j]max(dp[j],dp[j-1]);}prevtemp;// 更新 prev}}returndp[m];}};图解空间优化text1 abcde, text2 ace (n5, m3) 初始化 dp [0, 0, 0, 0] i1 (a): j1: prev0, temp0, aa? 是 - dp[1]prev11, prev0 j2: prev0, temp0, a!c - dp[2]max(0,0)0, prev0 j3: prev0, temp0, a!e - dp[3]max(0,0)0, prev0 dp [0, 1, 0, 0] i2 (b): j1: prev0, temp1, b!a - dp[1]max(1,0)1, prev1 j2: prev1, temp0, b!c - dp[2]max(0,0)0, prev0 j3: prev0, temp0, b!e - dp[3]max(0,0)0, prev0 dp [0, 1, 0, 0] i3 (c): j1: prev0, temp1, c!a - dp[1]max(1,0)1, prev1 j2: prev1, temp0, cc? 是 - dp[2]prev12, prev0 j3: prev0, temp0, c!e - dp[3]max(0,0)0, prev0 dp [0, 1, 2, 0] i4 (d): j1: prev0, temp1, d!a - dp[1]max(1,0)1, prev1 j2: prev1, temp2, d!c - dp[2]max(2,0)2, prev2 j3: prev2, temp0, d!e - dp[3]max(0,0)0, prev0 dp [0, 1, 2, 0] i5 (e): j1: prev0, temp1, e!a - dp[1]max(1,0)1, prev1 j2: prev1, temp2, e!c - dp[2]max(2,0)2, prev2 j3: prev2, temp0, ee? 是 - dp[3]prev13, prev0 dp [0, 1, 2, 3] 答案dp[3] 3 OK空间复杂度O(min(n,m))五、记忆化搜索递归版思路从后往前递归如果字符匹配则 1否则取两种情况的最大值。classSolution{public:intlongestCommonSubsequence(string text1,string text2){intntext1.size(),mtext2.size();vectorvectorintmemo(n,vectorint(m,-1));returndfs(n-1,m-1,text1,text2,memo);}private:intdfs(inti,intj,stringtext1,stringtext2,vectorvectorintmemo){if(i0||j0)return0;if(memo[i][j]!-1)returnmemo[i][j];if(text1[i]text2[j]){memo[i][j]dfs(i-1,j-1,text1,text2,memo)1;}else{memo[i][j]max(dfs(i-1,j,text1,text2,memo),dfs(i,j-1,text1,text2,memo));}returnmemo[i][j];}};六、与第5题最长回文子串对比维度第5题 最长回文子串第1143题 最长公共子序列字符串数量1 个字符串2 个字符串dp 维度二维但方向确定二维两个方向状态定义dp[i][j] s[i…j] 是否回文dp[i][j] s1[0…i-1] 和 s2[0…j-1] 的 LCS转移方程dp[i][j] s[i]s[j] dp[i1][j-1]dp[i][j] match ? dp[i-1][j-1]1 : max(dp[i-1][j], dp[i][j-1])遍历方向从小到大长度递增从小到大i, j 递增复杂度分析方法时间复杂度空间复杂度备注暴力搜索O(2^(nm))O(nm)会超时记忆化搜索O(n*m)O(n*m)剪枝优化动态规划O(n*m)O(n*m)最常用空间优化O(n*m)O(min(n,m))面试加分面试追问 FAQ问题回答要点Q: 为什么 dp[i][j] max(dp[i-1][j], dp[i][j-1])当两个字符不匹配时必须丢弃 text1 或 text2 的最后一个字符。丢弃 text1 取 dp[i-1][j]丢弃 text2 取 dp[i][j-1]Q: 如果要输出 LCS 本身怎么办需要额外一个 path 数组记录转移方向最后从 dp[n][m] 回溯到起点Q: LCS 和 LCSubstring 的区别LCS 是子序列不连续LCSubstring 是子串连续Q: 时间复杂度能否优化到 O(nm)不能LCS 问题是 NPC 问题目前已知最优是 O(n*m)Q: 如果 text1 和 text2 很长怎么办可以用滚动数组优化空间到 O(min(n,m))相关题目题目编号题目名称难度核心差异5最长回文子串中等单字符串连续子串72编辑距离困难三维 DP字符串匹配1143最长公共子序列中等基础题两个字符串718最长重复子数组中等两个数组连续子数组1035不相交的线中等LCS 变种连线不相交1458两个子序列的最大点积中等DP 最大乘积总结要点内容核心思想动态规划text1 和 text2 两个维度状态定义dp[i][j] text1[0…i-1] 和 text2[0…j-1] 的 LCS 长度转移方程match ? dp[i-1][j-1] 1 : max(dp[i-1][j], dp[i][j-1])初始化dp[0][] 0, dp[][0] 0空字符串空间优化一维数组prev 保存左上角值与第5题对比单字符串变双字符串状态定义不同LCS 是经典的二维动态规划问题掌握后可以轻松解决类似的两字符串匹配问题。
