【Day 57 】2022-02-06 - 1143.最长公共子序列

[azl397985856]

1143.最长公共子序列

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/longest-common-subsequence

前置知识

• 数组
• 动态规划

  题目描述

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

一个字符串的   子序列   是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 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 <= 1000 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

[Brent-Liu]

class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(), n = text2.length(); vector<vector> dp(m + 1, vector(n + 1)); for (int i = 1; i <= m; i++) { char c1 = text1.at(i - 1); for (int j = 1; j <= n; j++) { char c2 = text2.at(j - 1); if (c1 == c2) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } };

[yetfan]

思路 最后一位相同 f[i][j] = f[i-1][j-1] + 1 最后一位不同则有2种可能性, f[i][j] = max(f[i-1][j], f[i][j-1])

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        f = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    f[i][j] = f[i-1][j-1] + 1
                else:
                    f[i][j] = max(f[i-1][j], f[i][j-1])
        return f[m][n]

复杂度 时间 O(mn) 空间 O(mn)

[zhangzz2015]

思路

• 典型的两维dp， dp[i][j] 为 string1 到 i 和 string2 到 j 情况最长公共子序列。时间复杂度为 O(nm)，空间复杂度为O(nm)，可进一步压缩到1维。
• dp[i, j] if(text1[i] == text2[j]) dp[i][j] = dp[i-1][j-1]+1;
• else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {

        //  dp[i, j]   if(text1[i] == text2[j])  dp[i][j] = dp[i-1][j-1]+1; 
        //                  else     dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
        int n = text1.size(); 
        int m = text2.size(); 
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); 

        for(int i=0; i< n; i++)
        {            
            for(int j=0; j< m; j++)
            {
                if(text1[i]== text2[j])
                    dp[i+1][j+1] = dp[i][j]+1;
                else
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); 
            }
        }        
        return dp[n][m];         
    }
};

[charlestang]

思路

动态规划。假设，dp[i][j] 表示前i个第一个字符串和前j个字符第二个字符串的最长公共子序列的长度。

不难看出，第 i 个字符和 第 j 个字符相等的时候 dp[i][j] = dp[i-1][j-1] + 1

而不等的时候， dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

时间复杂度 O(mn)

空间复杂度 O(mn)

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)

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

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text2[j-1] == text1[i-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

[falconruo]

思路:

动态规划，二维数组dp[i][j]表示第一个字符串text1的前i个字符的子串与第二个字符串text2的前j个字符的子串的最长公共子序列的长度, 其状态转移方程如下：

1. text1[i] == text2[j]，则dp[i][j] = dp[i - 1][j - 1] + 1
2. text1[i] != text2[j]，则dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), 前 i - 1 个字符的子串sub_text1和前 j 个字符串的子串sub_text2的最长公共子序列的长度 l1, 前 i 个字符的子串sub_text1和前 j - 1 个字符串的子串sub_text2的最长公共子序列的长度 l2, 取较大者

复杂度分析:

• 时间复杂度: O(N * M), N, M为两个字符串长度
• 空间复杂度: O(N * M)

代码(C++):

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length();
        int n = text2.length();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; ++i) //dp[i]
            for (int j = 1; j <= n; ++j) // dp[j]
                if (text1[i - 1] == text2[j - 1]) // string are 0-based
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

        return dp[m][n];
    }
};

[laofuWF]

# dp[i][j]: longest common sequence with text1[0:i+1] and text2[0:j+1]
# loop through text1 and text2
# if letter at i from text1 == letter at j from text2: dp[i][j] = dp[i - 1][j - 1] + 1
# else: (not matching), candidates are either from dp of prev substring of text1 and current substring of text2
#   or from dp of current substring of text1 and prev substring of text2. 
#   AKA remove letter at i from text1 or remove letter at j from text2

# time: O(m*n)
# space: O(m*n)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # add another row/col for base cases
        dp = [[0 for i in range(len(text2) + 1)] for j in range(len(text1) + 1)]

        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[-1][-1]

[tongxw]

思路

dp(i, j) = dp(i-1, j-1) + 1 if s1[i] == s1[j] else max(dp(i-1, j), dp(i, j-1))

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];
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                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-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[m][n];
    }
}

TC: O(mn) SC:O(mn)

[feifan-bai]

思路 1.二维DP

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]

复杂度分析

• 时间复杂度：O(M*N)
• 空间复杂度：O(M*N)

[xinhaoyi]

1143. 最长公共子序列

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

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

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

思路一

动态规划

状态转移方程

dp(i,j)=dp(i−1)(j−1)+1, 当 text1[i - 1] == text2[j - 1];text1[i−1]==text2[j−1]; dp[i][j] = max(dp(i - 1)(j), dp(i)(j - 1)dp(i)(j)=max(dp(i−1)(j),dp(i)(j−1), 当 text1[i - 1] != text2[j - 1]text1[i−1]!=text2[j−1]

代码

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];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                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 - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[M][N];
    }
}

复杂度分析

时间复杂度：$O(mn)$

空间复杂度：$O(mn)$

[ZhangNN2018]

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """

        n1, n2 = len(text1), len(text2)
        pre = [0 for _ in range(n2 + 1)]
        dp = [0 for _ in range(n2 + 1)]
        for i in range(n1):
            for j in range(1, n2 + 1):
                if text1[i] == text2[j-1]:
                    dp[j] = pre[j-1] + 1
                else:
                    dp[j] = max(pre[j], dp[j-1])
                pre[j-1] = dp[j-1]
            pre[j] = dp[j]
        return dp[-1]

[didiyang4759]

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    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];
    }
}

[yan0327]

func longestCommonSubsequence(text1 string, text2 string) int {
    m,n := len(text1),len(text2)
    dp := make([][]int,m+1)
    for i:=0;i<m+1;i++{
        dp[i] = make([]int,n+1)
    }
    for i:=1;i<m+1;i++{
        for j:=1;j<n+1;j++{
            if text1[i-1] == text2[j-1]{
                dp[i][j] = dp[i-1][j-1]+1
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}
func max(a,b int) int{
    if a > b{
        return a
    }
        return b
}

[ZacheryCao]

Idea

DP

Code

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(1+len(text2))] for _ in range(len(text1)+1)]
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[i+1][j+1] = dp[i][j]+1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i][j], dp[i+1][j])
        return dp[-1][-1]

Complexity:

Time: O(MN) Space: O(MN)

[Tesla-1i]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)

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

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text2[j-1] == text1[i-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

[Toms-BigData]

【Day 57】1143.最长公共子序列

思路

二维dp

golang代码

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n:=len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    max := func(a, b int) int {
        if a>b{
            return a
        }
        return b
    }
    for i, c1 := range text1 {
        for j, c2 := range text2 {
            if c1 == c2{
                dp[i+1][j+1] = dp[i][j] + 1
            }else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            }
        }
    }
    return dp[m][n]
}

复杂度

时间:O(mn) 空间:O(mn)

[LAGRANGIST]

day57-1143.最长公共子序列

Problem

给定两个字符串 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 仅由小写英文字符组成。

思路

• dp
• 状态转移方程：

$$ \begin{equation} dp{i+1j+1}=\left{ \begin{aligned} & dp{ij} + 1 \ & max(dp{i{j+1}},dp{i+1j}) \end{aligned} \right. \end{equation} $$

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int dp[1010][1010]; //dp[i][j]为 1...i 和 1...j 最长 LCS 长度

        for(int i = 1; i <= text1.size(); i++)
        {
            for(int j = 1;j <= text2.size(); j++)
            {
                if(i == 0 || j == 0)
                {
                    dp[i][j] = 0;
                }
                else if(text1[i-1] == text2[j-1]) // WRONG: else if(text1[i-1] == text2[j-1])
                {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                }
                else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

复杂度

• 时间和空间都是 $O(n^2)$

注意点

• 代码中标注WRONG的位置写错了一开始导致输入为 text1 = "a",text2 = "b"的时候输出为 1，因为判断的是 a 和 b后一个位置的字母（不存在)

[QinhaoChang]

class Solution: def dp(self, text1, text2, s1, s2, lookup): if s1 == len(text1) or s2 == len(text2): return 0 if lookup[s1][s2] == -1: if text1[s1] == text2[s2]: lookup[s1][s2] = 1 + self.dp(text1, text2, s1+1, s2+1, lookup) else: lookup[s1][s2] = max(self.dp(text1, text2, s1+1, s2, lookup), self.dp(text1, text2, s1, s2+1, lookup)) return lookup[s1][s2]

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    return self.dp(text1, text2, 0, 0, [[-1 for _ in range(len(text2))] for _ in range(len(text1))])

[CoreJa]

思路

太菜了，二维动规都忘了七七八八了。

• DP：二维动规，设dp[i][j]为text1[:i]和text2[:j]的最长公共子序列。这个定义出来了，一切就都好解决了，复杂度$O(n^2)$。考虑任一dp[i][j]：
  • 若此时有text1[i]==text2[j]，那说明当前两个子串text1[:i-1]和text2[:j-1]他们再加上当前字母text1[i]/text2[j]后，正好使它们的公共子串长度加1。也就是$dp[i][j]=dp[i-1][j-1]+1$
  • 否则则是text1[i]!=text2[j]，那么可以考虑为text1[:i]在text2[:j-1]的情况下增加了一个不相干的字符text2[j]，也可以看作是text2[:j]在text1[:i-1]的情况下增加了一个不相关的字符text1[i]，结果保持不变。两种情况显然取最大值。即$dp[i][j]=max(dp[i-1][j],dp[j-1][i])$
• 滚动DP：上述改进，每个单元格的更新仅与上方，左方和左上方的单元格相关，所以可以将二维数组变成滚动的一维数组(需要保留两行，否则左上角更新会被影响)。复杂度$O(n^2)$

代码

class Solution:
    # DP：二维动规，设`dp[i][j]`为`text1[:i]`和`text2[:j]`的最长公共子序列。这个定义出来了，一切就都好解决了，复杂度$O(n^2)$。
    # 考虑任一`dp[i][j]`：
    # - 若此时有`text1[i]==text2[j]`，那说明当前两个子串`text1[:i-1]`和`text2[:j-1]`他们再加上当前字母
    #   `text1[i]`/`text2[j]`后，正好使它们的公共子串长度加1。也就是$dp[i][j]=dp[i-1][j-1]+1$
    # - 否则则是`text1[i]!=text2[j]`，那么可以考虑为`text1[:i]`在`text2[:j-1]`的情况下增加了一个不相干的字符`text2[j]`，
    #   也可以看作是`text2[:j]`在text1[:i-1]的情况下增加了一个不相关的字符`text1[i]`，结果保持不变。两种情况显然取最大值。
    #   即$dp[i][j]=max(dp[i-1][j],dp[j-1][i])$
    def longestCommonSubsequence1(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        text1 = "^" + text1
        text2 = "^" + text2
        for i, j in product(range(1, m + 1), range(1, n + 1)):
            if text1[i] == text2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

    # 滚动DP：上述改进，每个单元格的更新仅与上方，左方和左上方的单元格相关，所以可以将二维数组变成滚动的一维数组(需要保留两行，
    # 否则左上角更新会被影响)。复杂度$O(n^2)$
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [0] * (n + 1)
        for i in range(m):
            dp_tmp = dp.copy()
            for j in range(n):
                if text1[i] == text2[j]:
                    dp[j] = dp_tmp[j - 1] + 1
                else:
                    dp[j] = max(dp[j - 1], dp[j])
        return dp[-2]

[tangjy149]

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        for(int i=1;i<text1.size()+1;i++){
            for(int j=1;j<text2.size()+1;j++){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

[LuoXingbiao]

思路

动态规划，dp[i][j]表示text1的前i个字符和text2得而前j个字符的公共子序列长度，目标为dp[m][n],m,n分别为text1和text2字符串的长度。状态转移方程，i，j指向的字符相同时dp[i][j] = dp[i - 1][j - 1] + 1，不同时dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])。

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){
                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]);
                }
            }
        }

        return dp[len1][len2];
    }
}

复杂度分析

时间复杂度：O(mn)

空间复杂度：O(mn)

[alongchong]

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    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];
    }
}

[Tao-Mao]

Idea

2d array to record all the possible length of common subsequence of i, j.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int t1 = text1.length();
        int t2 = text2.length();
        int[][] dp = new int[t1+1][t2+1];
        for (int i = 1; i <= t1; ++i) {
            for (int j = 1; j <= t2; ++j) {
                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-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[t1][t2];
    }
}

Complexity

Space: O(nm) Time: O(nm)

[CodingProgrammer]

思路

DP

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            throw new IllegalArgumentException();
        }

        char[] chs1 = text1.toCharArray(), chs2 = text2.toCharArray();
        int length1 = chs1.length, length2 = chs2.length;
        // dp[i][j] 表示以 i - 1 结尾的 text1 和 以 j - 1 结尾的 text2 的最长公共子序列的长度
        // if (t1[i] == t2[j]) dp[i][j] = dp[i - 1][j - 1] + 1
        // if (t1[i] != t2[j]) dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1])
        int[][] dp = new int[length1 + 1][length2 + 1];
        // dp[0][j] = 0, dp[i][0] = 0
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (chs1[i - 1] == chs2[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[length1][length2];
    }
}

复杂度

• Time : O(M*N)
• Space: O(M*N)

[yijing-wu]

// dynamic programming
// TC = O(M*N)  SC = O(M*N)

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];     // default value is 0
        for(int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for(int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if( c1 == c2) {
                    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];
    }
}

[watchpoints]

代码 c++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        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] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

[Bochengwan]

思路

一维数组dp,利用两个数组,减少空间复杂度。

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        dp = [0]*(m+1)
        for i in range(1,n+1):
            ndp = [0]*(m+1)
            for j in range(1,m+1):
                if text1[i-1] == text2[j-1]:
                    ndp[j] = dp[j-1]+1
                else:
                    ndp[j] = max(dp[j],ndp[j-1])
            dp = ndp
        return dp[m] 

复杂度分析

• 时间复杂度：O(MN)
• 空间复杂度：O(min(M,N))

[LannyX]

思路

DP

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int l1 = text1.length(), l2 = text2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        //dp[1] -> text[0]
        for(int i = 1; i <= l1; i++){
            for(int j = 1; j <= l2; j++){           
                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 - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[l1][l2];
    }
}

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

[cszys888]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m):
            for j in range(n):
                if text1[i] == text2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        return dp[m][n]

time complexity: O(mn) space complexity: O(mn)

[Richard-LYF]

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: len1, len2 = len(text1)+1, len(text2)+1 dp = [[0 for in range(len1)] for in range(len2)] # 先对dp数组做初始化操作 for i in range(1, len2): for j in range(1, len1): # 开始列出状态转移方程 if text1[j-1] == text2[i-1]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[-1][-1]

[zol013]

from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        '''
        dp = [[0 for j in range(len(text2)+1)] for i in range(len(text1)+1)]
        for i in range(len(text1)-1 ,-1 ,-1):
            for j in range(len(text2)-1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = dp[i+1][j+1]+1
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])
        return dp[0][0]
        '''

        @lru_cache(maxsize=None)

        def memo_solve(p1 ,p2):
            '''
            if p1 == len(text1) or p2 == len(text2):
                return 0
            option_1 = memo_solve(p1+1, p2)

            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1+1, first_occurence + 1)

            return max(option_1, option_2)

        return memo_solve(0,0)
        '''
            if p1 == len(text1) or p2 == len(text2):
                return 0

            if text1[p1] == text2[p2]:
                return 1+ memo_solve(p1+1, p2+1)
            else:
                return max(memo_solve(p1, p2+1),memo_solve(p1+1, p2))
        return memo_solve(0,0)

[XinnXuu]

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    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];
    }
}

复杂度

• 时间复杂度：O(m*n)
• 空间复杂度：O(m*n)

[herbertpan]

思路

1. subsequence：肯定不是sliding window或者two pointers
2. longest: 可能是dp

3. string和string的compare，那就得是二维d p

   code

   class Solution {
   public int longestCommonSubsequence(String text1, String text2) {
       int m = text1.length();
       int n = text2.length();
   
       int[][] LCSMatrix = new int[m][n];
       int LCS = 0;
   
       for (int row = 0; row < LCSMatrix.length; row++) {
           for (int col = 0; col < LCSMatrix[0].length; col++) {
               int topLeft = row - 1 >= 0 && col - 1 >= 0 ? LCSMatrix[row - 1][col - 1] : 0;
               int topRight = row - 1 >= 0 ? LCSMatrix[row - 1][col] : 0;
               int bottomLeft = col - 1 >= 0 ? LCSMatrix[row][col - 1] : 0;
   
               if (text1.charAt(row) == text2.charAt(col)) {
                   // but it cannot pass max of its matching coiunt
                   LCSMatrix[row][col] = topLeft + 1;
               } else {
                   LCSMatrix[row][col] = Math.max(topLeft, Math.max(topRight, bottomLeft));
               }
   
               LCS = Math.max(LCS, LCSMatrix[row][col]);
           }
       }
   
       return LCS;
   }
   }

   complexicy

4. time: O(MN)
5. space: O(MN)

[zhiyuanpeng]

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        ans = 0
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return ans

[HWFrankFung]

Codes

var longestCommonSubsequence = function (text1, text2) {
    this.dp = function (i, j) {
        if (i === -1 || j === -1) {
            return 0;
        }
        if (text1[i] === text2[j]) {
            return this.dp(i - 1, j - 1) + 1;
        } else {
            return Math.max(
                this.dp(i - 1, j);
                this.dp(i, j - 1);
                this.dp(i - 1, j - 1) ;
            );
        }
    }
    return this.dp(text1.length - 1, text2.length - 1);
};

[jiaqiliu37]

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        ans = 0
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return ans

[1149004121]

1143. 最长公共子序列

思路

动态规划。

代码

function longestCommonSubsequence(text1: string, text2: string): number {
    const m = text1.length, n = text2.length;
    let dp = new Array(n + 1).fill(0);
    let pre = 0, temp = 0;
    for(let j = 0; j < m; j++){
        temp = dp[0];
        for(let i = 0; i < n; i++){
            pre = temp;
            temp = dp[i + 1];
            if(text1[j] === text2[i]){
                dp[i + 1] = pre + 1;
            }else{
                dp[i + 1] = Math.max(dp[i], dp[i + 1]);
            }
        }
    };
    return dp[n];
};

复杂度分析

• 时间复杂度：O(NM)。
• 空间复杂度：O(N)。

[z1ggy-o]

思路

动态规划还需要大量的练习和理解。

今天的题目看了题解才能勉强理解。

最基本的解题思路是，依次遍字符串的每个字符，我们可以求得以某个字符为开始或结束的最长公共子序列。 暴力枚举有许多重复的工作，DP 避免了它们。

假设有 i，j 两个 indices 分别从前向后的分别指向 text1，text2 两个字符串的字符。 问题的子问题是：以 text[i] 结尾的 text1 和 text2 最长公共子序列有多长，text2 的 j 自然的要从头遍历到尾。 则有，text[i] == text[j] 时，最长公共子序列的长度在之前的长度上加一。 如果不相等，则维持之前的最长公共子序列长度，即 text1[i-1] 或 text[j-1]时的长度。

让 dp[i][j] 表示 text1[i], text2[j] 结尾时的最长公共子序列长度。有转移方程：

• if text[i] == text[j], dp[i][j] = dp[i-1][j-1] + 1;
• else, dp[i][j] = max(dp[i][j-1], dp[i-1][j])

需要注意的是，基本 state 是一个字符都没有的时候。

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int M = text1.size();
        const int N = text2.size();

        vector<vector<int>> dp(M+1, vector<int>(N+1, 0));

        int lcs = 0;
        // -1 because we add a state that has no chars, and treat it as 0th state.
        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] = max(dp[i-1][j], dp[i][j-1]);
                }
                lcs = max(lcs, dp[i][j]);
            }
        }

        return lcs;
    }
};

复杂度分析

• 时间：O(MN)，双层遍历。
• 空间：O(MN)

[JudyZhou95]

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)

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

        for i in range(m):
            for j in range(n):
                if text1[i] == text2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

        return dp[-1][-1]

复杂度

TC:O(MN) SC: O(MN)

[declan92]

思路

1. dp[i][j]表示text1[?:i]text2[?:j]包含text1[i],text2[j]最长公共子序列长度;
2. text1[i]=text2[j]时,dp[i][j] = dp[i-1][j-1] +1;text1[i] != text2[j],dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
3. 初始dp[0][0] = 0;
4. 嵌套循环 java code

   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];
       int ans = 0;
       for(int i = 0;i<m;i++){
           for(int j = 0;j<n;j++){
               if(text1.charAt(i)==text2.charAt(j)){
                   dp[i+1][j+1] = dp[i][j]+1;                  
               }else{
                   dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
               }
               ans = Math.max(ans, dp[i+1][j+1]);
           }
       }
       return ans;
   }
   }

   时间:$O(mn)$
   空间:$O(mn)$

[baddate]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(), n=text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(text1[i] == text2[j])
                    dp[i+1][j+1] = dp[i][j] + 1;
                else
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            }
        return dp[m][n];
    }
};

复杂度分析

• 时间：O(MN)
  • 空间：O(MN)

[GaoMinghao]

思路

1. dp[i][j]表示a[0:i] b[0:j] 的时候公共子序列的最长长度
2. dp[i+1][j+1] 可能：1. a[i+1] b[j+1] 都不选 2. a[i+1]选，b[j+1]选，3.a[i+1]不选，b[j+1]选，4. a[i+1] b[j+1]都选（这种情况需要a[i+1] == b[j+1]）,合并情况1，2，3

   代码

   class Solution {
   public int longestCommonSubsequence(String text1, String text2) {
       int m = text1.length(), n = text2.length();
       char[] a = text1.toCharArray();
       char[] b = text2.toCharArray();
       int[][] dp = new int[m+1][n+1];
       for(int i = 1; i <= m; i++) {
           for(int j = 1; j <= n; j++) {
               dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
               if(a[i-1] == b[j-1])
                   dp[i][j] = Math.max(dp[i-1][j-1]+1, dp[i][j]);
           }
       }
       return dp[m][n];
   }
   }

   时间复杂度

   O(N^2)

[Serena9]

代码

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        ans = 0
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return ans

[callmeerika]

思路

动态规划

代码

var longestCommonSubsequence = function(text1, text2) {
    let m = text1.length;
    let n = text2.length;
    let arr = new Array(m + 1).fill(0).map(vv=>new Array(n + 1).fill(0));
    for(let i = 1; i <= m;i++) {
        for(let j = 1; j <= n; j++) {
            if(text1[i-1] === text2[j-1]) {
                arr[i][j] = arr[i-1][j-1] + 1;
            } else {
                arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j]);
            }
        }
    }
    return arr[m][n];
};

复杂度

时间复杂度：O(mn)
空间复杂度：O(mn)

[hdyhdy]

思路： 动态规划

func longestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i,t1 := range text1{
        for j,t2 := range text2{
            if t1 == t2 {
                dp[i+1][j+1] = dp[i][j] + 1 
            }else {
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
            }
        } 
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间复杂度：O（nm） 空间复杂度：O(mn)

[Aobasyp]

思路 动态规划

class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector> dp(text1.size() + 1, vector(text2.size() + 1, 0)); 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] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[text1.size()][text2.size()]; } }; 时间复杂度：O(m n) 空间复杂度：O(m n)

[zwx0641]

class Solution { public int longestCommonSubsequence(String text1, String text2) { int[][] dp = new int[text1.length() + 1][text2.length() + 1];

    for (int j = 0; j <= text1.length(); j++) {
        dp[j][0] = 0;
    }

    for (int j = 0; j <= text2.length(); j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= text1.length(); i++) {
        for (int j = 1; j <= text2.length(); j++) {
            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 - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[text1.length()][text2.length()];
}

}

[guangsizhongbin]

func longestCommonSubsequence(text1, text2 string) int { m, n := len(text1), len(text2) dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } for i, c1 := range text1 { for j, c2 := range text2 { if c1 == c2 { dp[i+1][j+1] = dp[i][j] + 1 } else { dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) } } } return dp[m][n] }

func max(a, b int) int { if a > b { return a } return b }

[ZJP1483469269]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        ans = 0
        for i in range(1,n + 1):
            for j in range(1 , m + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    ans = max(ans,dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return ans

[junbuer]

思路

• 二维动态规划 对于$dp[i][j]$存在两种情况:
  • 如果两个字符串最后一位相同则有：$dp[i][j] = dp[i - 1][j - 1] + 1$
  • 如果不同：$dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])$

    代码

    class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
    """
    :type text1: str
    :type text2: str
    :rtype: int
    """
    m = len(text1)
    n = len(text2)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

    复杂度分析

• 时间复杂度：$O(m * n)$
• 空间复杂度：$O(m * n)$

[wbcz]

class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]); dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]); } } return dp[m][n]; } }