【Day 57 】2023-04-11 - 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 输入的字符串只含有小写英文字符。

[Meisgithub]

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

[JiangyanLiNEU]

• DP
• T = O(MN)

• S = O(MN)

  class Solution {
  public:
  int longestCommonSubsequence(string text1, string text2) {
      int one = text1.size();
      int two = text2.size();
      int dp[one][two];
  
      for (int row = 0; row < one; row++){
          for (int col = 0; col < two; col++){
              if (row == 0 && col == 0){
                  dp[row][col] = int(text1[row]==text2[col]);
              } else if (row == 0){
                  dp[row][col] = max(dp[row][col-1], int(text1[row]==text2[col]));
              } else if (col == 0){
                  dp[row][col] = max(dp[row-1][col], int(text1[row]==text2[col]));
              } else {
                  dp[row][col] = max(max(dp[row-1][col-1]+int(text1[row]==text2[col]), dp[row-1][col]), dp[row][col-1]);
              }
          }
      }
      return dp[one-1][two-1];
  }
  };

[tzuikuo]

思路

动态规划

代码

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=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]);
                }
            }
        }
        return dp[m][n];
    }
};

复杂度分析

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

[Zoeyzyzyzy]

class Solution {
    //tips: 单个数组/字串用dp时，将dp[i]定义为nums[0:i]中想要的结果，
    // 两个数组/字串用dp时，将其定义为dp[i][j]，含义为在A[0:i]和B[0:j]之间匹配得到想要的结果

    /* 
     * 定义：dp[i][j]为text1[0:i-1]和text2[0:j-1]的最长公共子序列，
     * 这样表示可以在i = 0||j =0时，dp[i][j] 为空字符串和另一个字符串的匹配结果，便于初始化为0
     * 递推公式：如果当前（i- 1) 与(j - 1)字符相同，则目前结果+1，若不同，则结果等于dp[i][j - 1], dp[i - 1][j]中的较大者。（画图可以清晰表示）
     * 初始化：空字符串与另一个字符串的比较结果始终为0
     * 遍历顺序：从小到大
     */

    //Time Complexity: O(mn), Space Complexity: O(mn)
    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][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }

    //递归版本，没有用缓存，会超时
    String text1, text2;
    public int longestCommonSubsequence1(String text1, String text2) {
        this.text1 = text1;
        this.text2 = text2;
        return dfs(text1.length(), text2.length());
    }

    private int dfs(int len1, int len2) {
        if (len1 == 0 || len2 == 0)
            return 0;
        if (text1.charAt(len1 - 1) == text2.charAt(len2 - 1))
            return dfs(len1 - 1, len2 - 1) + 1;
        return Math.max(dfs(len1 - 1, len2), dfs(len1, len2 - 1));
    }
}

[Abby-xu]

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

[LIMBO42]

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

[kofzhang]

思路

动态规划，二维。 当两个值相等的时候取左上值+1，不相等的时候取上面或左面最大值

复杂度

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

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1 = len(text1)
        l2 = len(text2)
        dp = [[0]*(l2+1) for _ in range(l1+1)]
        for i in range(1,l1+1):
            for j in range(1,l2+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[l1][l2]

[aoxiangw]

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] = 1 + dp[i][j]
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

        return dp[m][n]

time, space: O(mn), O(mn)

[jmaStella]

int[][] m = new int[s.length() +1][t.length() +1];
        for (int i=s.length()-1; i>=0; i--) {
            for (int j=t.length()-1; j>=0; j--) {
                if (s.charAt(i) == t.charAt(j)) {
                    m[i][j] = m[i+1][j+1] + 1;
                } else {
                    m[i][j] = Math.max(m[i+1][j], m[i][j+1]);
                }
            }
        }
        return m[0][0];

[NorthSeacoder]

 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    //dp[i][j] 以text1[i-1]结尾的字符串和以 text2[j-1]结尾的字符串的最长公共子序列长度;
    const lenA = text1.length;
    const lenB = text2.length;
    const dp = new Array(lenA + 1).fill().map(() => new Array(lenB + 1).fill(0));
    //dp[i][j]
    //text1[i-1]===text2[j-1](有共同元素):dp[i][j] = dp[i-1][j-1]+1;
    //text1[i-1]===text2[j-1]:max(dp[i][j-1],dp[i-1][j]);
    let res = 0;
    for (let i = 1; i <= lenA; i++) {
        for (let j = 1; j <= lenB; 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]);
            }
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
};

[bookyue]

TC: O(n*m)
SC: O(m)

    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[] f = new int[m + 1];
        for (int i = 0; i < n; i++) {
            int prev = f[0];
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (text1.charAt(i) == text2.charAt(j))
                    f[j + 1] = prev + 1;
                else
                    f[j + 1] = Math.max(f[j + 1], f[j]);

                prev = tmp;
            }
        }

        return f[m];
    }

[harperz24]

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)]

        # 在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果
        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]

        # 2d
        # time: O(mn)
        # space: O(mn)

[FireHaoSky]

思路：动态规划，顺序不需要连续，两个字符串分别做横坐标和纵坐标

代码：python

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(n*m)
空间复杂度：O(mn)
"""

[JasonQiu]

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

[wangqianqian202301]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(X, Y, m, n):
            if m == 0 or n == 0:
                return 0
            elif X[m-1] == Y[n-1]:
                return 1 + lcs(X, Y, m-1, n-1)
            else:
                return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
        return lcs(text1, text2, len(text1), len(text2))

[csthaha]

let m = text1.length,
        n = text2.length,
        dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for(let i = 1; i <= m; i++) {
        const c1 = text1[i  -1];
        for(let j = 1; j <= n; j++) {
            const c2 = text2[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]

[Fuku-L]

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for(int i = 1; i<=text1.length(); i++){
            char a = text1.charAt(i-1);
            for(int j = 1; j <= text2.length(); j++){
                char b =text2.charAt(j-1);
                if(a == b){
                    dp[i][j] = dp[i-1][j-1]+1;
                } else{
                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

复杂度分析

• 时间复杂度：O(N*M)，其中 N,M分别为两个字符串的长度。
• 空间复杂度：O(N*M)

[Diana21170648]

思路

动态规划+数组

class Slution:
    def longestseries(self,text1:str,text2:str)-> int:
        m,n=len(text1),len(text2)
        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 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

**复杂度分析**
- 时间复杂度：O(m*n)，其中 m，n 为数组长度，双重循环
- 空间复杂度：O(m*n)，相当于二维数组

[Hughlin07]

class Solution {

public int longestCommonSubsequence(String t1, String t2) {
    int[] memo = new int[t2.length() + 1];
    char[] t1c = t1.toCharArray(), t2c = t2.toCharArray();
    for (int i = t1c.length - 1; i > -1; i--) {
        int previousRigth = 0, newRight = 0;
        for (int j = t2c.length - 1; j > -1; j--) {
            int tmp = memo[j];
            int max;
            if (t1c[i] == t2c[j]) max = previousRigth + 1;
            else max = Math.max(tmp, newRight);
            memo[j] = newRight = max;
            previousRigth = tmp;
        }
    }
    return memo[0];
}

}

[texamc2]

func longestCommonSubsequence(s, t string) int {
    m := len(t)
    f := make([]int, m+1)
    for _, x := range s {
        pre := 0 // f[0]
        for j, y := range t {
            if x == y {
                f[j+1], pre = pre+1, f[j+1]
            } else {
                pre = f[j+1]
                f[j+1] = max(f[j+1], f[j])
            }
        }
    }
    return f[m]
}

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

[chocolate-emperor]

class Solution {
public:
//   两个字符串的所有公共子序列集合中的最长值
//   划分标准：字符串最后一元素是否包含在子序列中(相等、不相等)  dp[i][j]代表到前i个和前j个为止的结果
//   dp[i][j]  = dp[i-1][j-1] + 1 都包含的前提是相等
//    i 0 j 0 , i 1 j 0 , i 0 j 1 , i 1 j 1
//   dp[i][j] = dp[i-1][j-1] , dp[i][j-1], dp[i-1][j]
//   from dp[1][1]  to  dp[m][n]
// 
    int dp[1004][1004];
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        if(m==0 || n == 0)  return 0;

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

    }
};

[yingchehu]

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

複雜度 Time: O(m n) Space: O(m n)

[kangliqi1]

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

[Lydia61]

1143. 最长公共子序列

思路

动态规划、二维数组

代码

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)

[zhangyu1131]

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

        //dp数组
        vector<vector<int>> dp(n, vector<int>(m, 0)); // dp[i][j]表示test1[0..i]和test2[0...j]的最长公共子序列长度
        // 初始化
        dp[0][0] = text1[0] == text2[0] ? 1 : 0;
        for (int i = 1; i < n; ++i)
        {
            if (text1[i] == text2[0])
            {
                dp[i][0] = 1;
            }
            else
            {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int i = 1; i < m; ++i)
        {
            if (text1[0] == text2[i])
            {
                dp[0][i] = 1;
            }
            else
            {
                dp[0][i] = dp[0][i - 1];
            }
        }

        // 递推
        for (int i = 1; i < n; ++i)
        {
            for (int j = 1; j < m; ++j)
            {
                if (text1[i] == 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]);
                }
            }
        }

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

[wangzh0114]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(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];
    }
};

[lp1506947671]

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

复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别为 A 和 B 的 长度。
• 空间复杂度：O(m * n)，其中 m 和 n 分别为 A 和 B 的 长度。

[Jetery]

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

[bingzxy]

思路

定义状态 dp[i][j]，为字符串 text1.substring(0, i), text2.substring(0,j) 最大公共子序列的长度。 转移方程为 dp[i][j] = dp[i-1][j-1] + 1，当text1中下标 i 的字符和text2中下标 j 的字符相等时；dp[i][j] = Math.max(dp[i-1], dp[i][j-1]，当两字符串结尾字符不相等时

代码

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

复杂度分析

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

[joemonkeylee]

思路

mark

代码

     public int LongestCommonSubsequence(string text1, string text2)
        {
            int m = text1.Length, n = text2.Length;
            int[,] dp = new int[m, n];
            dp[0, 0] = text1[0] == text2[0] ? 1 : 0;
            for (int j = 1; j < n; j++)
            {
                dp[0, j] = text1[0] == text2[j] ? 1 : dp[0, j - 1];
            }
            for (int i = 1; i < m; i++)
            {
                dp[i, 0] = text1[i] == text2[0] ? 1 : dp[i - 1, 0];
            }
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    if (text1[i] == text2[j])
                        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 - 1, n - 1];
        }

复杂度分析

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

[snmyj]

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()];
    }
};

[X1AOX1A]

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

[RestlessBreeze]

code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<int> temp(text1.length() + 1);
        vector<vector<int>> dp(text2.length() + 1, temp);

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