1143. Longest Common Subsequence LeetCode Solution
In this guide, you will get 1143. Longest Common Subsequence LeetCode Solution with the best time and space complexity. The solution to Longest Common Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Example 2:
Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.
Example 3:
Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.
1143. Longest Common Subsequence LeetCode Solution in C++
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
const int m = text1.length();
const int n = text2.length();
// dp[i][j] := the length of LCS(text1[0..i), 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];
}
}; /* code provided by PROGIEZ */
1143. Longest Common Subsequence LeetCode Solution in Java
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
final int m = text1.length();
final int n = text2.length();
// dp[i][j] := the length of LCS(text1[0..i), 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];
}
} // code provided by PROGIEZ
1143. Longest Common Subsequence LeetCode Solution in Python
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
# dp[i][j] := the length of LCS(text1[0..i), 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] # code by PROGIEZ
