1143.最长公共子序列

题目描述

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

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

• 例如，"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。

两个个字符串的公共子序列是这两个字符串所共同拥有的子序列

示例1：

输入：text1 = "abcde"， text2 = "ace"
输出：3
解释：最长公共子序列是"ace"，它的长度为3。

示例2：

输入：text1 = "abc"， text2 = "abc"
输出：
解释：最长公共子序列是"abc"，它的长度为3。

示例3：

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

提示：

• 1<=text1.length,text2.length<=1000
• text1和text2仅由小写英文字母组成。

解题思路

1. 确定dp数组的含义
dp[i][j]：以0到i-1长度的字符串text1和以0到j-1长度的字符串text2的最长公共子序列为dp[i][j]
2. 递推公式
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])
3. dp数组初始化
dp[i][0] =dp[0][j] = 0
4. 遍历顺序
从左往右，从上往下
5. 打印dp数组

代码实现

• 核心模式

class Solution{
public:
    int longestCommonSubsequence(string text1, string text2){
        // initialize the DP array
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        // traversal 
        for (int i = 1; i <= text1.size(); i++){
            for (int j = 1; j <= text2.size(); j++){
                if (text1[i - 1] == text2[j -1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        print2DVector(dp);

        return dp[text1.size()][text2.size()];
    }
};

• ACM模式

"dynamicPro.h"

#include <iostream>
#include "dynamicPro.h"

class Solution{
public:
    int longestCommonSubsequence(string text1, string text2){
        // initialize the DP array
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        // traversal 
        for (int i = 1; i <= text1.size(); i++){
            for (int j = 1; j <= text2.size(); j++){
                if (text1[i - 1] == text2[j -1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        print2DVector(dp);

        return dp[text1.size()][text2.size()];
    }
};

int main(){
    Solution solution;
    cout << "Result1's Dp array = " << solution.longestCommonSubsequence("abcde", "ace") << endl;
    cout << "Result2's Dp array = " << solution.longestCommonSubsequence("abc", "abc") << endl;
    cout << "Result3's Dp array = " << solution.longestCommonSubsequence("abc", "def") << endl;

    return 0;
}

• 输出

Result1's Dp array = [[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 2], [0, 1, 2, 3]]
3
Result2's Dp array = [[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 3]]
3
Result3's Dp array = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
0