1092. Shortest Common Supersequence.txt

https://leetcode.com/problems/shortest-common-supersequence/


class Solution {
private:
    string subs(string str1,string str2){
        string dp[str1.size() + 1][str2.size() + 1];
        for(int i = 0 ; i < str1.size(); i++){
            for(int j = 0; j < str2.size(); j++){
                if(str1[i] == str2[j]){
                    dp[i+1][j+1] = dp[i][j] + str1[i];
                }
                else{
                    dp[i+1][j+1] = dp[i][j+1].size() > dp[i+1][j].size() ? dp[i][j+1] : dp[i+1][j];
                }                                                                                  
            }
        }
        return dp[str1.size()][str2.size()];
    }
public:
    string shortestCommonSupersequence(string str1, string str2) {
        if(str1.size() == 0)
            return "";
        int i = 0;
        int j = 0;
        string res = "";
        for(char c : subs(str1,str2)){
            while(str1[i] != c)
                res+= str1[i++];
            while(str2[j] != c)
                res+=str2[j++];
            res+=c;
            i++;
            j++;
        }
        
        return res + str1.substr(i,str1.size()) + str2.substr(j,str2.size());
    }
};