Longest Common Subsequence | Introduction & LCS Length
all three solution.
1. first one is recursion
2. second one is Memorization using top down approach
3. dynamic programming using a 2d matrix filling from top using bottom up approach
complete example is here
really nice video
//longest comman subsequence
//watch this video for more detail
//https://www.youtube.com/watch?v=sSno9rV8Rhg
let r=0;//check how many call happen using Recursion
let m=0;//check how many call happen using Memoization top down appoarch
let d=0;//check how many call happen using dynamic programming bottom up appoarch
//using Recursion
String.prototype.subsequence=function(str2,len1=0,len2=0)
{
r++;
//check if either of them is undefined return 0
if(this[len1]===undefined || str2[len2]===undefined)
{
return 0;
}
//if matched move to next in both string
else if(this[len1]===str2[len2])
{
return 1+this.subsequence(str2,++len1,++len2);
}
else
{
//get max value out of tewo and return it
return Math.max(this.subsequence(str2,++len1,len2),this.subsequence(str2,len1,++len2))
}
}
let str1="manishchauhanppq";
let str2="manchanq";
console.log(str1.subsequence(str2)+"===="+r);
//Memoization using top down appoarch
String.prototype.subsequenceM=function(str2,tempArray,len1=this.length,len2=str2.length)
{
m++;
//check if either of them is undefined return 0
if(len1===0 || len2===0)
{
return 0;
}
if(tempArray[len1-1][len2-1]!==-1)
{
return tempArray[len1-1][len2-1];
}
if(this[len1-1]===str2[len2-1])
{
tempArray[len1-1][len2-1]=1+this.subsequenceM(str2,tempArray,len1-1,len2-1);
}else
{
tempArray[len1-1][len2-1]=Math.max(this.subsequenceM(str2,tempArray,len1-1,len2),
this.subsequenceM(str2,tempArray,len1,len2-1));
}
return tempArray[len1-1][len2-1];
}
//create a array of m*n length
let tempArray=Array(str1.length).fill(Array(str2.length).fill(-1));
console.log(str1.subsequenceM(str2,tempArray)+"==calls drops to==="+m);
//dynamic programming using top down appoarch
String.prototype.subsequenceD=function(str2)
{
let tempArray=Array(str1.length+1).fill(Array(str2.length+1).fill(0));
for(let i=1;i<tempArray.length;i++)
{
for(let j=1;j<tempArray[0].length;j++)
{
if(this[i-1]===str2[j-1])
{
tempArray[i][j]=1+tempArray[i-1][j-1];
}
else
{
tempArray[i][j]=Math.max(tempArray[i-1][j],tempArray[i][j-1])
}
}
}
return tempArray[i-1][j-1];
}
console.log("XMJYAUZ".subsequenceD("MZJAWXU"));
Comments
Post a Comment