• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
const int m = text1.length();
const int n = text2.length();
// dp[i][j] := LCS's length of text1[0..i) and text2[0..j)
vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
dp[i + 1][j + 1] = text1[i] == text2[j]
? 1 + dp[i][j]
: max(dp[i][j + 1], dp[i + 1][j]);

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

## JAVA

``````class Solution {
public int longestCommonSubsequence(String text1, String text2) {
final int m = text1.length();
final int n = text2.length();
// dp[i][j] := LCS's length of text1[0..i) and text2[0..j)
int[][] dp = new int[m + 1][n + 1];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
dp[i + 1][j + 1] = text1.charAt(i) == text2.charAt(j)
? 1 + dp[i][j]
: Math.max(dp[i][j + 1], dp[i + 1][j]);

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

## Python

``````class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
# dp[i][j] := LCS's length of text1[0..i) and text2[0..j)
dp = [[0] * (n + 1) for _ in range(m + 1)]

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

return dp[m][n]
``````