Longest Common Substring using recursion, memorization and dynamic programming

working example


https://stackblitz.com/edit/js-isyptv?file=index.js

running code

//Longest Common Substring using recursion 1

let r1=0;

let m1=0;

String.prototype.subStringR=function(str2,r=this.length,c=this.length,count=0)

{

     r1+=1;

    if(r===0 || c===0)

    {

      return count;

    }

 

    if(this[r-1]===str2[c-1])

    {

      count=this.subStringR(str2,r-1,c-1,count+1);

    }

      

    count=Math.max(count,this.subStringR(str2,r-1,c,0),this.subStringR(str2,r,c-1,0));

      return count;

}

let s1="zxabcdezy";

let s2="yzabcdezx";

console.time();

console.log(s1.subStringR(s2)+"---",r1);

console.timeEnd();

//2nd using using memorize

String.prototype.subStringM=function(str2,r=0,c=0,count=0,memo=[])

{

    m1+=1;

    if(r===0 || c===0)

    {

      return count;

    }

    if(this[r-1]===str2[c-1])

    {

      count=this.subStringM(str2,r-1,c-1,count+1,memo);

      memo[r-1][c-1]=count;

    }

    if( memo[r-1][c-1]!==-1)

      {

        return memo[r-1][c-1]

      }

      memo[r-1][c-1]=Math.max(count,this.subStringM(str2,r-1,c,0,memo),this.subStringM(str2,r,c-1,0,memo));

      return  memo[r-1][c-1];

}

let str1="zxabcdezy";

let str2="yzabcdezx";

let memo=Array(str1.length).fill(Array(str2.length).fill(-1));

console.time();

console.log(str1.subStringM(str2,r=str1.length,c=str2.length,0,memo)," "+m1);

console.timeEnd();

//dp using dynamic programming

String.prototype.subStringDP=function(str)

{

  let dp=Array(this.length+1).fill(Array(str.length+1).fill(0));

  let result=0;

  for(let i=1;i<dp.length;i++)

  {

    for(let j=1;j<dp[0].length;j++)

    {

         if(this[i]===str[j])

         {

            dp[i][j]=1+dp[i-1][j-1];

            result=Math.max(result, dp[i][j])

         }

          

    } 

  }

  return result;

}

let strdp1="manishex";

let strdp2="shex";

console.time();

console.log(strdp1.subStringDP(strdp2));

console.timeEnd();