Shortest Common Supersequence

class Solution {
public:
    string shortestCommonSupersequence(string a, string b) {
        int n = a.size(), m = b.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1
                                                : max(dp[i - 1][j], dp[i][j - 1]);
        string out;
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (a[i - 1] == b[j - 1]) { out += a[--i]; --j; }
            else if (dp[i - 1][j] > dp[i][j - 1]) out += a[--i];
            else out += b[--j];
        }
        while (i > 0) out += a[--i];
        while (j > 0) out += b[--j];
        reverse(out.begin(), out.end());
        return out;
    }
};

func shortestCommonSupersequence(a string, b string) string {
    n, m := len(a), len(b)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    out := []byte{}
    i, j := n, m
    for i > 0 && j > 0 {
        if a[i-1] == b[j-1] {
            i--
            out = append(out, a[i])
            j--
        } else if dp[i-1][j] > dp[i][j-1] {
            i--
            out = append(out, a[i])
        } else {
            j--
            out = append(out, b[j])
        }
    }
    for i > 0 {
        i--
        out = append(out, a[i])
    }
    for j > 0 {
        j--
        out = append(out, b[j])
    }
    for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
        out[l], out[r] = out[r], out[l]
    }
    return string(out)
}

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        out = []
        i, j = n, m
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                i -= 1
                out.append(str1[i])
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
                out.append(str1[i])
            else:
                j -= 1
                out.append(str2[j])
        while i > 0:
            i -= 1
            out.append(str1[i])
        while j > 0:
            j -= 1
            out.append(str2[j])
        return ''.join(reversed(out))

function shortestCommonSupersequence(a, b) {
    const n = a.length, m = b.length;
    const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let 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] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    const out = [];
    let i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] === b[j - 1]) {
            i--;
            out.push(a[i]);
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
            out.push(a[i]);
        } else {
            j--;
            out.push(b[j]);
        }
    }
    while (i > 0) { i--; out.push(a[i]); }
    while (j > 0) { j--; out.push(b[j]); }
    return out.reverse().join('');
}

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        StringBuilder out = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                i--;
                out.append(str1.charAt(i));
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
                out.append(str1.charAt(i));
            } else {
                j--;
                out.append(str2.charAt(j));
            }
        }
        while (i > 0) { i--; out.append(str1.charAt(i)); }
        while (j > 0) { j--; out.append(str2.charAt(j)); }
        return out.reverse().toString();
    }
}

function shortestCommonSupersequence(a: string, b: string): string {
    const n = a.length, m = b.length;
    const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let 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] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    const out: string[] = [];
    let i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] === b[j - 1]) {
            i--;
            out.push(a[i]);
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
            out.push(a[i]);
        } else {
            j--;
            out.push(b[j]);
        }
    }
    while (i > 0) { i--; out.push(a[i]); }
    while (j > 0) { j--; out.push(b[j]); }
    return out.reverse().join('');
}