1092. Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

class Solution {
    string LCS(string& A, string& B) {
        int N = A.length(), M = B.length();
        vector<vector<int>> dp(N+1, vector<int>(M+1));
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(A[i-1] == B[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        string lcs = "";
        while(N and M) {
            if(A[N-1] == B[M-1]) {
                lcs += A[N-1];
                N--,M--;
            } else if(dp[N-1][M] > dp[N][M-1]) N--;
            else M--;
        }
        reverse(begin(lcs),end(lcs));
        return lcs;
    }
    string helper(string& str1, string& str2) {
        string lcs = LCS(str1, str2);
        int i = 0, j = 0, n = str1.length(), m = str2.length(), idx = 0, k = lcs.length();
        string res = "";
        while(idx < k) {
            while(i < n and str1[i] != lcs[idx]) res += str1[i++];
            while(j < m and str2[j] != lcs[idx]) res += str2[j++];
            res += lcs[idx++]; i++,j++;
        }
        while(i < n) res += str1[i++];
        while(j < m) res += str2[j++];
        return res;
    }
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string lcs = LCS(str1, str2);
        int i = 0, j = 0, n = str1.length(), m = str2.length(), idx = 0, k = lcs.length();
        string res = "";
        while(idx < k) {
            while(i < n and str1[i] != lcs[idx]) res += str1[i++];
            while(j < m and str2[j] != lcs[idx]) res += str2[j++];
            res += lcs[idx++]; i++,j++;
        }
        while(i < n) res += str1[i++];
        while(j < m) res += str2[j++];
        return res;
    }
};