Longest Common Subsequence Leetcode Solution
Longest Common Subsequence Leetcode Problem :
Given two stringstext1 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”.
Example :
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Longest Common Subsequence Leetcode Solution :
Constraints :
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English characters.
Example 1:
- Input: text1 = “abc”, text2 = “abc”
- Output: 3
- Explanation: The longest common subsequence is “abc” and its length is 3.
Intuition :
The problem requires finding the length of the longest common subsequence (LCS) between two given strings, text1 and text2. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
To solve this problem, we can use dynamic programming. We’ll create a 2D matrix, dp, where dp[i][j] represents the length of the LCS between the first i characters of text1 and the first j characters of text2.
Approach :
- Initialize a 2D matrix, dp, with dimensions (m + 1) x (n + 1) (where m is the length of text1 and n is the length of text2). Initialize all values in dp to 0.
- Iterate through text1 from index 1 to m (both inclusive), and for each character text1[i – 1]:
- Iterate through text2 from index 1 to n (both inclusive), and for each character text2[j – 1]:
- If text1[i – 1] is equal to text2[j – 1], update dp[i][j] as dp[i – 1][j – 1] + 1. This means the current characters match, so the LCS length increases by 1.
- Otherwise, take the maximum of dp[i – 1][j] (the LCS length without considering text1[i – 1]) and dp[i][j – 1] (the LCS length without considering text2[j – 1]), and assign it to dp[i][j]. This handles the case when the current characters don’t match, so we need to consider the LCS length without one of the characters.
- Finally, return dp[m][n], which represents the length of the LCS between text1 and text2.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length();
int n = text2.length();
int k = max(m,n);
vector prev(k+1,0), cur(k+1,0);
// vector>dp(m+1,vector(n+1,-1));
//Base Cases for Tabulation without space optimization
// for(int i=0;i<=m;i++){
// dp[i][0]= 0;
// }
// for(int j=0;j<=n;j++){
// dp[0][j]= 0;
// }
for(int ind1=1;ind1<=m;ind1++){
for(int ind2=1;ind2<=n;ind2++){
if(text1[ind1-1]== text2[ind2-1]){
cur[ind2] = 1+ prev[ind2-1];
}
else {
cur[ind2]= max(prev[ind2],cur[ind2-1]);
}
}
prev = cur;
}
return prev[n];
}
};
Java
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length()][text2.length()];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], -1);
}
return helper(text1, text2, 0, 0, dp);
}
public int helper(String s1, String s2, int i, int j, int[][] dp) {
if (i == s1.length() || j == s2.length()) return 0;
if (dp[i][j] != -1) return dp[i][j];
if (s1.charAt(i) == s2.charAt(j)) return dp[i][j] = helper(s1, s2, i + 1, j + 1, dp) + 1;
return dp[i][j] = Math.max(helper(s1, s2, i + 1, j, dp), helper(s1, s2, i, j + 1, dp));
}
}
Python
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 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]
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment