LeetCode 1143、最长公共子序列

视频地址：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];
    }
};

3、Python 代码

dp数组长度为n1*n2

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp数组大小为 n1*n2
        # dp[i][j]表示text1[:i+1]和text2[:j+1]的最长公共子序列
        # 换句话说，以text1[i]为结尾和以text2[j]为结尾的两个子串，的最长公共子序列
        n1, n2 = len(text1), len(text2)
        dp = [[0] * n2 for _ in range(n1)]
        # 初始化dp数组
        # flag1标志用于表示，是否前面出现text1[i] == text2[0]
        # 如果出现，则始终修改为1
        flag1 = False
        for i in range(n1):
            if text1[i] == text2[0] or flag1:
                dp[i][0] = 1
                flag1 = True
        # flag2标志用于表示，是否前面出现text1[0] == text2[j]
        # 如果出现，则始终修改为1
        flag2 = False
        for j in range(n2):
            if text1[0] == text2[j] or flag2:
                dp[0][j] = 1
                flag2 = True

        for i in range(1, n1):
            for j in range(1, n2):
                # 注意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]

dp数组长度为(n1+1)*(n2+1)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp数组大小为 (n1+1)*(n2+1)
        # dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列
        # 换句话说，以text1[i-1]为结尾和以text2[j-1]为结尾的两个子串，的最长公共子序列
        n1, n2 = len(text1), len(text2)
        # dp数组的第一行，第一列，均为0，无需做其他的额外初始化
        dp = [[0] * (n2+1) for _ in range(n1+1)]
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                # 注意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]