Shortest Common Super Sequence Geeks For Geeks
class Solution
{
//Function to find the length of the shortest common supersequence of two strings.
public static int shortestCommonSupersequence(String x,String y,int n,int m)
{
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(x.charAt(i-1)==y.charAt(j-1)){
t[i][j]=t[i-1][j-1]+1;
}
else{
t[i][j]=Integer.max(t[i][j-1],t[i-1][j]);
}
}
}
int c=t[n][m];
return n+m-c;
}
}
TIME:O(N*M) [Nested Arrays] [Geeks For Geeks Time:0.3/1.5]
SPACE:O(N*M)[2D array is used]
Thanks for Reading.😇
"Share further to increase knowledge treasure.😊"
Comments
Post a Comment