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 :



public class Solution {
    public int solve(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]

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

Popular posts from this blog

Solutions Of Practice Questions Dated 01-06-2022

-
Question 1: Transmit the Message: Solution: import java.util.*; class Solution{     public static void main(String arg[]){         Scanner sc=new Scanner(System.in);         String s=sc.next();                          ArrayList<Integer>aa=new ArrayList<Integer>();         ArrayList<Character>ab=new ArrayList<Character>();                  char flag=s.charAt(0);        int index=0;        int count=1;         for(int i=1;i<s.length();i++){             if(flag==s.charAt(i)){                 count++;             }             else{                 aa.add(index,count);                 ab.add(index,flag);                 count=1;                 flag=s.charAt(i);                 index++;             }         }         aa.add(index,count);         ab.add(index,flag);                  int max=Collections.max(aa);                  for(int i=aa.size()-1;i>0;i--){             if(aa.get(i)==max){                 flag=ab.get(i);                 break;             }
Read more

CODEFORCES SPY DETECTED ROUND 713

-
 import java.util.*; public class CodeForcesSpyDetected{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); ArrayList <Integer> aa=new ArrayList<Integer>();  while(t -->0){ int n=sc.nextInt(); int arr2[]=new int[n]; for(int i=0;i<n;i++){ arr2[i]=sc.nextInt(); } for(int i=0;i<n;i++){ aa.add(arr2[i]); } for(int i=0;i<aa.size();i++){ //System.out.println(Collections.frequency(aa,aa.get(i))); if(Collections.frequency(aa,aa.get(i))==1){ System.out.println((i+1)); aa.clear(); break; } } } } }
Read more

Maximum Winning Score Geeks For Geeks

-
Problem Link: https://practice.geeksforgeeks.org/problems/4ead9c3991a3822f578309e2232bc5415ac35cb9/1# It is also the problem of the day for 5 march. Solution: class Solution {     public static Long findMaxScore(Node root)     {         Node temp=root;         long sum=0;         while(temp!=null){             if(temp.right==null && temp.left==null){                 return (long) temp.data;             }             else{                 return (long) temp.data*Long.max(findMaxScore(temp.left),findMaxScore(temp.right));             }         }         return sum;     } } Time Complexity:[GFG Time:0.7/2.9] Space Complexity: O(N)[Number of nodes given in tree] Auxiliary Space: O(1) Approach Used: Here we used an approach that we will traverse recursively. And when we travel recursive we follow the bottom to the top approach of the tree.  It means we will see the leaf node and then move up to the tree.  For recursion, we should have a base condition and that is when node. right or
Read more