class Solution {
public:
    string shortestCommonSupersequence(string s1, string s2) {

        vector<vector<int>> dp(s1.length() + 1, vector<int>(s2.length() + 1, 0));

        for (int i = 0; i <= s1.length(); i++) dp[i][s2.length()] = s1.length() - i;
        for (int i = 0; i <= s2.length(); i++) dp[s1.length()][i] = s2.length() - i;

        for (int i1 = s1.length() - 1; i1 >= 0; i1--) {
            for (int i2 = s2.length() - 1; i2 >= 0; i2--) {
                if (s1[i1] == s2[i2]) {
                    dp[i1][i2] = 1 + dp[i1 + 1][i2 + 1];
                 //   mapx[{i1, i2}] = s1[i1];
                } else {
                    int t1 = dp[i1 + 1][i2];
                    int t2 = dp[i1][i2 + 1];
                    if (t1 < t2) {
                      //  mapx[{i1, i2}] = s1[i1];
                    } else {
                      //  mapx[{i1, i2}] = s2[i2];
                    }
                    dp[i1][i2] = min(t1, t2);
                }
            }
        }

        string ans = "";
        int m = s1.length();
        int n = s2.length();
        int i = 0, j = 0;

        while (i < m && j < n) {
            if (s1[i] == s2[j]) {
                ans += s1[i];
                i += 1;
                j += 1;
            } else {
                if (dp[i + 1][j] < dp[i][j + 1]) {
                    ans += s1[i];
                    i += 1;
                } else {
                    ans += s2[j];
                    j += 1;
                }
            }
        }

        while (i < m) {
            ans += s1[i];
            i += 1;
        }

        while (j < n) {
            ans += s2[j];
            j += 1;
        }

        return ans;
    }
};