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 (p

shortestCommonSupersequence.js

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
// Function to find the longest common subsequence (LCS) of two strings
function findLCS(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // Fill the DP table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[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]);
            }
        }
    }

    // Reconstruct the LCS from the DP table
    let lcs = '';
    let i = m;
    let j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            lcs = str1[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return lcs;
};

// Function to find the shortest common supersequence (SCS) using the LCS
var shortestCommonSupersequence = function(str1, str2) {
    const lcs = findLCS(str1, str2);
    let i = 0;
    let j = 0;
    let k = 0;
    let scs = '';

    // Merge str1 and str2 based on the LCS
    while (k < lcs.length) {
        while (i < str1.length && str1[i] !== lcs[k]) {
            scs += str1[i];
            i++;
        }
        while (j < str2.length && str2[j] !== lcs[k]) {
            scs += str2[j];
            j++;
        }
        scs += lcs[k];
        i++;
        j++;
        k++;
    }

    // Add any remaining characters from str1 and str2
    scs += str1.slice(i);
    scs += str2.slice(j);

    return scs;
};