LC1143. 最长公共子序列

LC1143. 最长公共子序列 视频地址：https://uha.xet.tech/s/2vvMzO

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1： 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 示例 2： 输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。 提示： 1 <= text1.length, text2.length <= 1000 text1 和 text2 仅由小写英文字符组成。

题目解析

参考代码（吴师兄）

1、Java 代码 // 登录 AlgoMooc 官网获取更多算法图解 // https://www.algomooc.com // 作者：程序员吴师兄 // 代码有看不懂的地方一定要私聊咨询吴师兄呀 // 最长公共子序列（ LeetCode 1143 ）：https://leetcode-cn.com/problems/longest-common-subsequence class Solution { public int longestCommonSubsequence(String text1, String text2) {

// 获取字符串 text1 的长度 int m = text1.length();

// 获取字符串 text2 的长度 int n = text2.length();

// 设置数组 dp，用来存储 text1 和 text2 最长公共子序列的长度 // dp[0][0] 表示 text1 前 0 个字符和 text2 前 0 个字符的最长公共子序列的长度 // dp[2][3] 表示 text1 前 2 个字符和 text2 前 3 个字符的最长公共子序列的长度 // dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度 // 前 i 个字符的区间为 [ 0 ， i - 1 ] // dp[m][n] 表示 text1 前 m 个字符和 text2 前 n 个字符的最长公共子序列的长度 // 前 m 个字符的表示区间为 [ 0 ,m ]，前 n 个字符的表示区间为 [ 0 ,n ] // 因此，dp 数组的长度为 m + 1 和 n + 1 int[][] dp = new int[m + 1][n + 1];

// dp[0][0] 表示 text1 前 0 个字符和 text2 前 0 个字符的最长公共子序列的长度 // 此时，text1 没有字符，text2 也没有字符 // 因此，最长公共子序列的长度为 0 dp[0][0] = 0;

// 并且，text1 没有字符 或者 text2 没有字符时，最长公共子序列的长度都为 0 for( int i = 0 ; i <= m ; i++){ dp[i][0] = 0; }

for( int j = 0 ; j <= n ; j++){ dp[0][j] = 0; }

// i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个字符 for (int i = 1; i <= m; ++i) {

// j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个字符 for (int j = 1; j <= n; ++j) {

// 如果发现 text1 的当前字符，即位置为 i - 1 的字符 // 与 text2 的当前字符，即位置为 j - 1 的字符【相同】 // 此时，找到了一个公共字符，最长公共子序列的长度加 1 if (text1.charAt(i - 1) == text2.charAt(j - 1)) {

// dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度 // dp[i - 1][j - 1] 表示 text1 前 i - 1 个字符和 text2 前 j - 1 个字符的最长公共子序列的长度 // dp[i][j] 在 dp[i - 1][j - 1] 的基础上又找到了一个公共字符，只需要加 1 即可 dp[i][j] = dp[i - 1][j - 1] + 1;

// 否则，说明 text1 的当前字符，即位置为 i - 1 的字符 // 与 text2 的当前字符，即位置为 j - 1 的字符【不相同】 } else {

// dp[i - 1][j] 表示 text1 前 i - 1 个字符和 text2 前 j 个字符的最长公共子序列的长度 // dp[i][j - 1] 表示 text1 前 i 个字符和 text2 前 j - 1 个字符的最长公共子序列的长度 // 需要判断这两者谁更大 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // 最后返回结果 return dp[m][n]; } } 2、C++ 代码 class Solution { public: int longestCommonSubsequence(string text1, string text2) { // 获取字符串 text1 的长度 int m = text1.length();

// 获取字符串 text2 的长度 int n = text2.length();

// 设置数组 dp，用来存储 text1 和 text2 最长公共子序列的长度 // dp[0][0] 表示 text1 前 0 个字符和 text2 前 0 个字符的最长公共子序列的长度 // dp[2][3] 表示 text1 前 2 个字符和 text2 前 3 个字符的最长公共子序列的长度 // dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度 // 前 i 个字符的区间为 [ 0 ， i - 1 ] // dp[m][n] 表示 text1 前 m 个字符和 text2 前 n 个字符的最长公共子序列的长度 // 前 m 个字符的表示区间为 [ 0 ,m ]，前 n 个字符的表示区间为 [ 0 ,n ] // 因此，dp 数组的长度为 m + 1 和 n + 1 auto dp = vector < vector < int>> ( m + 1 ,vector<int> ( n + 1 ));

// dp[0][0] 表示 text1 前 0 个字符和 text2 前 0 个字符的最长公共子序列的长度 // 此时，text1 没有字符，text2 也没有字符 // 因此，最长公共子序列的长度为 0 dp[0][0] = 0;

// 并且，text1 没有字符 或者 text2 没有字符时，最长公共子序列的长度都为 0 for( int i = 0 ; i <= m ; i++){ dp[i][0] = 0; }

for( int j = 0 ; j <= n ; j++){ dp[0][j] = 0; }

// i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个字符 for (int i = 1; i <= m; ++i) {

// j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个字符 for (int j = 1; j <= n; ++j) {

// 如果发现 text1 的当前字符，即位置为 i - 1 的字符 // 与 text2 的当前字符，即位置为 j - 1 的字符【相同】 // 此时，找到了一个公共字符，最长公共子序列的长度加 1 if (text1[i - 1]== text2[j - 1]) {

// dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度 // dp[i - 1][j - 1] 表示 text1 前 i - 1 个字符和 text2 前 j - 1 个字符的最长公共子序列的长度 // dp[i][j] 在 dp[i - 1][j - 1] 的基础上又找到了一个公共字符，只需要加 1 即可 dp[i][j] = dp[i - 1][j - 1] + 1;

// 否则，说明 text1 的当前字符，即位置为 i - 1 的字符 // 与 text2 的当前字符，即位置为 j - 1 的字符【不相同】 } else {

// dp[i - 1][j] 表示 text1 前 i - 1 个字符和 text2 前 j 个字符的最长公共子序列的长度 // dp[i][j - 1] 表示 text1 前 i 个字符和 text2 前 j - 1 个字符的最长公共子序列的长度 // 需要判断这两者谁更大 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } // 最后返回结果 return dp[m][n]; } }; 3、Python 代码 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int:

获取字符串 text1 的长度

m = len(text1)

获取字符串 text2 的长度

n = len(text2)

设置数组 dp，用来存储 text1 和 text2 最长公共子序列的长度

dp[0][0] 表示 text1 前 0 个字符和 text2 前 0 个字符的最长公共子序列的长度

dp[2][3] 表示 text1 前 2 个字符和 text2 前 3 个字符的最长公共子序列的长度

dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度

前 i 个字符的区间为 [ 0 ， i - 1 ]

dp[m][n] 表示 text1 前 m 个字符和 text2 前 n 个字符的最长公共子序列的长度

前 m 个字符的表示区间为 [ 0 ,m ]，前 n 个字符的表示区间为 [ 0 ,n ]

因此，dp 数组的长度为 m + 1 和 n + 1

dp = [[0] * (n + 1 ) for _ in range( m + 1 )]

dp[0][0] 表示 text1 前 0 个字符和 text2 前 0 个字符的最长公共子序列的长度

此时，text1 没有字符，text2 也没有字符

因此，最长公共子序列的长度为 0

dp[0][0] = 0

并且，text1 没有字符 或者 text2 没有字符时，最长公共子序列的长度都为 0

for i in range( 0 , m + 1 ) : dp[i][0] = 0

for j in range( 0 , n + 1 ) : dp[0][j] = 0

i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个字符

for i in range( 1 , m + 1 ) :

j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个字符

for j in range( 1 , n + 1 ) :

如果发现 text1 的当前字符，即位置为 i - 1 的字符

与 text2 的当前字符，即位置为 j - 1 的字符【相同】

此时，找到了一个公共字符，最长公共子序列的长度加 1

if text1[i - 1] == text2[j - 1] :

dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度

dp[i - 1][j - 1] 表示 text1 前 i - 1 个字符和 text2 前 j - 1 个字符的最长公共子序列的长度

dp[i][j] 在 dp[i - 1][j - 1] 的基础上又找到了一个公共字符，只需要加 1 即可

dp[i][j] = dp[i - 1][j - 1] + 1

否则，说明 text1 的当前字符，即位置为 i - 1 的字符

与 text2 的当前字符，即位置为 j - 1 的字符【不相同】

else:

dp[i - 1][j] 表示 text1 前 i - 1 个字符和 text2 前 j 个字符的最长公共子序列的长度

dp[i][j - 1] 表示 text1 前 i 个字符和 text2 前 j - 1 个字符的最长公共子序列的长度

需要判断这两者谁更大

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

最后返回结果

return dp[m][n]

参考代码（许老师）

1、Java 代码 dp数组长度为n1*n2 class Solution { public int longestCommonSubsequence(String text1, String text2) { // dp数组大小为 n1*n2 // dp[i][j]表示text1[:i+1]和text2[:j+1]的最长公共子序列 // 换句话说，以text1[i]为结尾和以text2[j]为结尾的两个子串，的最长公共子序列 int n1 = text1.length(); int n2 = text2.length(); int[][] dp = new int[n1][n2]; // 初始化dp数组 // flag1标志用于表示，是否前面出现text1[i] == text2[0] // 如果出现，则始终修改为1 boolean flag1 = false; for (int i = 0; i < n1; i++) { if (text1.charAt(i) == text2.charAt(0) || flag1) { dp[i][0] = 1; flag1 = true; } } // flag2标志用于表示，是否前面出现text1[0] == text2[j] // 如果出现，则始终修改为1 boolean flag2 = false; for (int j = 0; j < n2; j++) { if (text1.charAt(0) == text2.charAt(j) || flag2) { dp[0][j] = 1; flag2 = true; } }

for (int i = 1; i < n1; i++) { for (int j = 1; j < n2; j++) { // 注意dp的定义，dp[i][j]需要考虑的是text1[i]和text2[j]是否相等 if (text1.charAt(i) == text2.charAt(j)) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } } } // 最后返回dp右下角的元素，索引为n1-1和n2-1 return dp[n1-1][n2-1]; } } dp数组长度为(n1+1)*(n2+1) class Solution { public int longestCommonSubsequence(String text1, String text2) { // dp数组大小为 (n1+1)*(n2+1) // dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列 // 换句话说，以text1[i-1]为结尾和以text2[j-1]为结尾的两个子串，的最长公共子序列 int n1 = text1.length(); int n2 = text2.length();

// dp数组的第一行，第一列，均为0，无需做其他的额外初始化 int[][] dp = new int[n1+1][n2+1];

for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { // 注意dp的定义，dp[i][j]需要考虑的是text1[i-1]和text2[j-1]是否相等 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][j-1], dp[i-1][j]); } } } // 最后返回dp右下角的元素，索引为n1和n2 return dp[n1][n2]; } }

2、C++ 代码 dp数组长度为n1*n2 class Solution { public: int longestCommonSubsequence(string text1, string text2) { // dp数组大小为 (n1+1)*(n2+1) // dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列 // 换句话说，以text1[i-1]为结尾和以text2[j-1]为结尾的两个子串，的最长公共子序列 int n1 = text1.size(); int n2 = text2.size();

// dp数组的第一行，第一列，均为0，无需做其他的额外初始化 vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));

for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { // 注意dp的定义，dp[i][j]需要考虑的是text1[i-1]和text2[j-1]是否相等 if (text1[i-1] == text2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } } // 最后返回dp右下角的元素，索引为n1和n2 return dp[n1][n2]; } };

dp数组长度为(n1+1)*(n2+1) class Solution { public: int longestCommonSubsequence(string text1, string text2) { // dp数组大小为 n1*n2 // dp[i][j]表示text1[:i+1]和text2[:j+1]的最长公共子序列 // 换句话说，以text1[i]为结尾和以text2[j]为结尾的两个子串，的最长公共子序列 int n1 = text1.size(); int n2 = text2.size();

vector<vector<int>> dp(n1, vector<int>(n2, 0));

// 初始化dp数组 // flag1标志用于表示，是否前面出现text1[i] == text2[0] // 如果出现，则始终修改为1 bool flag1 = false; for (int i = 0; i < n1; i++) { if (text1[i] == text2[0] || flag1) { dp[i][0] = 1; flag1 = true; } } // flag2标志用于表示，是否前面出现text1[0] == text2[j] // 如果出现，则始终修改为1 bool flag2 = false; for (int j = 0; j < n2; j++) { if (text1[0] == text2[j] || flag2) { dp[0][j] = 1; flag2 = true; } }

for (int i = 1; i < n1; i++) { for (int j = 1; j < n2; j++) { // 注意dp的定义，dp[i][j]需要考虑的是text1[i]和text2[j]是否相等 if (text1[i] == text2[j]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } } // 最后返回dp右下角的元素，索引为n1-1和n2-1 return dp[n1-1][n2-1]; } }