Longest Common Subsequence Dynamic Programming (Geeks For Geeks , LeetCode, InterviewBit)
LeetCode:
class Solution {
public int longestCommonSubsequence(String a, String b) {
int n=a.length();
int m=b.length();
int t[][]=new int[n+1][m+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<m+1;j++){
if(i==0 || j==0){
t[i][j]=0;
}
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<m+1;j++){
if(a.charAt(i-1)==b.charAt(j-1)){
t[i][j]=t[i-1][j-1]+1;
}
else{
t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);
}
}
}
return t[n][m];
}
}
TIME:O(N*M)[2 loops ie. nested][LeetCode Time: 18ms faster than 44.87% ]
SPACE:O(N*M)[Due to usage of 2d matrix][LeetCode Memory: 43.1 MB less than 36.27%]
For printing LCS refer to:
https://yashboss116.blogspot.com/2021/10/printing-longest-common-subsequence.html
And instead of returning t[n][m], you can write the logic mentioned in the function print of the above link provided.
********************************************************************************
Geeks For Geeks :
class Solution
{
//Function to find the length of longest common subsequence in two strings.
static int lcs( int m, int n, String s1, String s2)
{
int temp=n;
n=m;
m=temp;
int t[][]=new int[n+1][m+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<m+1;j++){
if(i==0 || j==0){
t[i][j]=0;
}
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<m+1;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
t[i][j]=1+t[i-1][j-1];
}
else{
t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);
}
}
}
return t[n][m];
}
}
TIME:O(N*M)[2 loops ie. nested][Geeks For Geeks Time: 0.4/1.4 ]
SPACE:O(N*M)[Due to usage of 2d matrix]
For printing LCS refer to:
https://yashboss116.blogspot.com/2021/10/printing-longest-common-subsequence.html
And instead of returning t[n][m], you can write the logic mentioned in the function print of the above link provided.
******************************************************************************
InterviewBit :
TIME:O(N*M)[2 loops ie. nested]
SPACE:O(N*M)[Due to usage of 2d matrix]
For printing LCS refer to:
https://yashboss116.blogspot.com/2021/10/printing-longest-common-subsequence.html
And instead of returning t[n][m], you can write the logic mentioned in the function print of the above link provided.
**********************************************************************************
Thanks For Reading😇.
"Share further to increase knowledge treasure.😊"
Comments
Post a Comment