LeetCode热题--1143. 最长公共子序列--中等

题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

题解

classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){char[]t=text2.toCharArray();intm=t.length;int[]f=newint[m+1];for(charx:text1.toCharArray()){intpre=0;// f[0]for(intj=0;j<m;j++){inttmp=f[j+1];f[j+1]=x==t[j]?pre+1:Math.max(f[j+1],f[j]);pre=tmp;}}returnf[m];}}

解析

出自：教你一步步思考动态规划：从记忆化搜索到递推（Python/Java/C++/Go）

classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){// 将 text2 转换为字符数组，便于快速访问每个字符char[]t=text2.toCharArray();// 获取 text2 的长度，记为 mintm=t.length;// 创建一维 DP 数组 f，长度为 m+1；f[j] 表示当前 text1 前缀与 text2[0..j-1] 的 LCS 长度// 初始时所有值为 0（因为未开始匹配）int[]f=newint[m+1];// 遍历 text1 中的每一个字符 xfor(charx:text1.toCharArray()){// pre 用于保存上一轮（即 text1 上一个字符处理时）的 f[j] 值，// 相当于二维 DP 中的 dp[i-1][j-1]intpre=0;// 对应 f[0]，即空字符串与任意前缀的 LCS 长度为 0// 遍历 text2 的每个位置 j（从 0 到 m-1）for(intj=0;j<m;j++){// 先保存当前 f[j+1] 的旧值（即上一行的 dp[i-1][j+1]），// 因为它将在下一次循环中作为 "pre"（即 dp[i-1][j]）使用inttmp=f[j+1];// 状态转移：// 如果当前字符 x == t[j]，说明可以扩展 LCS：f[j+1] = pre + 1// 否则，取不包含 x 或不包含 t[j] 的最大值：max(f[j+1], f[j])f[j+1]=x==t[j]?pre+1:Math.max(f[j+1],f[j]);// 更新 pre 为 tmp（即上一行的 f[j+1]），供下一次 j 循环使用pre=tmp;}}// 最终结果存储在 f[m] 中，表示 text1 与整个 text2 的 LCS 长度returnf[m];}}