class Solution {
public:
    void reverseStr(string& str)
    {
        int len = str.length();
        int n = len-1;
        int i = 0;
        while(i<=n)
        {

            swap(str[i],str[n]);
            n = n-1;
            i = i+1;
        }

    }

    string solve(string &str1, string &str2,int n,int m,int ind1,int ind2,string &temp,string &ans,int &min_len,vector<vector<pair<int,string>>> &dp)
    {
        if(ind1<0 && ind2<0)
        {
            if(temp.size()<=min_len)
            {
                ans=temp;
                min_len=temp.size();
            }
            return ans;
        }

        if(ind1<0)
        {
            for(int k=ind2;k>=0;k--)
                temp+=str2[k];
            if(temp.size()<=min_len)
            {
                ans=temp;
                min_len=temp.size();
            }
            return ans;
        }

        if(ind2<0)
        {
            for(int k=ind1;k>=0;k--)
                temp+=str1[k];
            if(temp.size()<=min_len)
            {
                ans=temp;
                min_len=temp.size();
            }
            return ans;
        }



        if(dp[ind1][ind2].first!=-1)
            return dp[ind1][ind2].second;


        if(str1[ind1] == str2[ind2])
        {
            temp+=str1[ind1];
            dp[ind1][ind2]={1,solve(str1,str2,n,m,ind1-1,ind2-1,temp,ans,min_len,dp)};
            temp.pop_back();
            return dp[ind1][ind2].second;
        }


        temp+=str1[ind1];
        string ans1=solve(str1,str2,n,m,ind1-1,ind2,temp,ans,min_len,dp);
        temp.pop_back();

        temp+=str2[ind2];
        string ans2=solve(str1,str2,n,m,ind1,ind2-1,temp,ans,min_len,dp);
        temp.pop_back();

        if(ans1.size()<=ans2.size())
            dp[ind1][ind2]={1,ans1};
        else
            dp[ind1][ind2]={1,ans2};

        return dp[ind1][ind2].second;

    }



    string shortestCommonSupersequence(string str1, string str2)
    {
        int n=str1.size();
        int m=str2.size();
        string temp="";
        string ans="";
        int min_len=INT_MAX;
        vector<vector<pair<int,string>>> dp(n,vector<pair<int,string>>(m,{-1,""}));
        solve(str1,str2,n,m,n-1,m-1,temp,ans,min_len,dp);
        reverseStr(ans);
        return ans;
    }
};