24 .Shortest Common SuperSequence

24. Shortest Common SuperSequence

Video link : https://youtu.be/823Grn4_dCQ
Problem Link: https://practice.geeksforgeeks.org/problems/shortest-common-supersequence0322/1

Code --------->>>>>>>>>>

//{ Driver Code Starts
//Initial template for C++

#include<bits/stdc++.h>
using namespace std;


// } Driver Code Ends
//User function template for C++


class Solution
{
    public:
    //Function to find length of shortest common supersequence of two strings.
    
    int LCS(string x,string y,int m,int n,vector<vector<int>> &dp)
    {
       
       if(m==0 || n==0)
       {
           return 0;
       }
       
       if(dp[m][n]!=-1)
       {
           return dp[m][n];
       }
       
       if(x[m-1]==y[n-1])
       {
           return dp[m][n]= 1+ LCS(x,y,m-1,n-1,dp);
       }
       else
       {
           return dp[m][n]= max(LCS(x,y,m-1,n,dp) , LCS(x,y,m,n-1,dp));
       }
       
        
    }
    
    int shortestCommonSupersequence(string x, string y, int m, int n)
    {
        //code here
        vector<vector<int>> dp (m+1,vector<int> (n+1,-1));
       int count=LCS(x,y,m,n,dp);
       
       return m+n-count;
       
    }
};

//{ Driver Code Starts.

int main()
{   
    
    int t;
    
    //taking total testcases
    cin >> t;
    while(t--){
    string X, Y;
    //taking String X and Y
	cin >> X >> Y;
	
	//calling function shortestCommonSupersequence()
	Solution obj;
	cout << obj.shortestCommonSupersequence(X, Y, X.size(), Y.size())<< endl;
    }
	return 0;
}


// } Driver Code Ends