AlgoPressAppearance
1143-最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence
给定两个字符串 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 。
提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
基本思路 【有问题，理解有问题】
参考 0392 首先区分短字符串和长字符串，然后用双指针判断 短 序列是否是 长 序列的子串，是的话，返回 短序列的长度，否则返回 0
参考代码
csharp
//示例 "bl" "yby" 应该返回 1， 不是 0
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
string strLong = text1;
string strShort = text2;
if(text2.Length > text1.Length){
strLong = text2;
strShort = text1;
}
//双指针
int sIndex = 0;
int tIndex = 0;
while(sIndex < strShort.Length && tIndex < strLong.Length){
if(strShort[sIndex] == strLong[tIndex]){
sIndex++;
}
tIndex++;
}
//看Short字符串的 Index 是否到底
return sIndex == strShort.Length ? strShort.Length : 0;
}
}
基本思路2：【动态规划：官方】
定义： dp 二维数组 dp[m+1,n+1] dp[i,j] 表示 text1[0:i] 和 text2[0:j] 的最大公共字符串长度 这里注意 i 和 j 表示长度为 i 和 j 的前缀，比如 text1[0:1] 就是 text1[0], text1[0:3] 表示 text[0..2]
比如 dp[1,1] 就表示 1位 text1 和 1位text2 最大公众字符串长度， 如果 text1[1-1] == text2[1-1] 时 dp[1,1] = 1
状态转移方程：
如果 text[i-1] == text[j-1] 则 dp[i,j] = dp[i-1,j-1] + 1 说明找到一个新的公共元素 如果 text[i-1] != text[j-1] 则 dp[i,j] = max(dp[i-1,j],dp[i,j-1])
参考代码
csharp
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
int m = text1.Length;
int n = text2.Length;
int[,] dp = new int[m+1,n+1];
//因为默认dp的值都为0，所以 dp[0,j] 和 dp[i,0] 都默认为0，不需要重新赋值
//从 1 开始循环
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(text1[i-1] == text2[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];
}
}
参考代码：复习2022-04-03
注意状态转移方程，有瑕疵 能匹配的时候，一定是 dp[i-1,j-1] + 1，因为这个单元格用掉匹配了 不能匹配的时候，应该选择 上面，或者左边 取最大值 (表示不选择text1最后一个字符，或者不选择text2最后一个字符)，而不是左上3个格子取最大值 注意 dp[m,n] 就是需要求解的最大值，不需要中间记录最大值 maxLength 了
csharp
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
//动态规划 dp[i,j] 表示 text1 截止前i个字符 和 text2 前j个字符 他们最大公共子序列的长度
int m = text1.Length;
int n = text2.Length;
int[,] dp = new int[m+1,n+1];
int maxLength = 0;
//初始化
dp[0,0] = 0;
//状态转移
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(text1[i-1] == text2[j-1]){
dp[i,j] = dp[i-1,j-1]+ 1;
}
else {
dp[i,j] = Math.Max(Math.Max(dp[i-1,j-1], dp[i-1,j]),dp[i,j-1]);
}
maxLength = Math.Max(maxLength,dp[i,j]);
}
}
return maxLength;
}
}
csharp
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
//动态规划 dp[i,j] 表示 text1 截止前i个字符 和 text2 前j个字符 他们最大公共子序列的长度
int m = text1.Length;
int n = text2.Length;
int[,] dp = new int[m+1,n+1];
//初始化
dp[0,0] = 0;
//状态转移
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(text1[i-1] == text2[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];
}
}
复习:20220515
注意 dp[i,j]表示前text1前i个字符和text2前j个字符的最长公共子序列的长度 所以判断的时候，要用 text1[i-1] == text2[j-1]
csharp
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
int m = text1.Length;
int n = text2.Length;
int[,] dp = new int[m+1,n+1]; //dp[i,j]表示前text1前i个字符和text2前j个字符的最长公共子序列的长度
for(int i=1; i<=m;i++){
for(int j=1; j<=n;j++){
if(text1[i-1] == text2[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]);
}
}
}
return dp[m,n];
}
}
复习：20220701
csharp
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
int m = text1.Length;
int n = text2.Length;
int[,] dp = new int[m+1,n+1]; //dp[i,j]表示前text1前i个字符和text2前j个字符的最长公共子序列的长度
for(int i=1; i<=m;i++){
for(int j=1; j<=n;j++){
dp[i,j] = text1[i-1] == text2[j-1] ? dp[i-1,j-1]+1 : Math.Max(dp[i,j-1],dp[i-1,j]);
}
}
return dp[m,n];
}
}