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.

&nbsp;
Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.


Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"


&nbsp;
Constraints:


	1 &lt;= str1.length, str2.length &lt;= 1000
	str1 and str2 consist of lowercase English letters.


class Solution:
    def shortestCommonSupersequence(self, A, B):
        n, m = len(A), len(B)
        dp = [B[:i] for i in range(m + 1)]
        for i in range(n):
            prev = A[:i]
            dp[0] = A[:i + 1]
            for j in range(m):
                if A[i] == B[j]:
                    prev, dp[j + 1] = dp[j + 1], prev + A[i]
                else:
                    prev, dp[j + 1] = dp[j + 1], min(dp[j] + B[j], dp[j + 1] + A[i], key = len)
        return dp[-1]
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m=str1.length();
        int n=str2.length();
        int[][] dp=new int[m+1][n+1];
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=1+dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        int i=m,j=n;
        String res="";
        while(i>0 && j>0){
            if(str1.charAt(i-1)==str2.charAt(j-1)){
                res=str1.charAt(i-1)+res;
                i--;
                j--;
            }else if(dp[i-1][j]>dp[i][j-1]){
                res=str1.charAt(i-1)+res;
                i--;
            }else{
                res=str2.charAt(j-1)+res;
                j--;
            }
        }
        while(i>0){
            res=str1.charAt(i-1)+res;
            i--;
        }
        while(j>0){
            res=str2.charAt(j-1)+res;
            j--;
        }
        return res;
    }
}
class Solution
{
    string LCS(string str1, string str2, int m, int n)
    {
        int t[m+1][n+1];
        string ans = "";
        for(int i = 0;i < m+1; ++i)
        {
            for(int j = 0; j< n+1; ++j)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

        for(int i = 1; i < m+1; ++i)
        {
            for(int j = 1; j < n+1; ++j)
            {
                if(str1[i-1] == str2[j-1])
                    t[i][j] = 1 + t[i-1][j-1];
                else
                    t[i][j] = max(t[i-1][j], t[i][j-1]);
            }
        }
        int i = m, j = n;
        while(i > 0 && j > 0)
        {
            if(str1[i-1] == str2[j-1])
            {
                ans.push_back(str1[i-1]);
                --i;
                --j;
            }

            else if(t[i][j-1] > t[i-1][j])
            {
                ans.push_back(str2[j-1]);
                --j;
            }

            else
            {
                ans.push_back(str1[i-1]);
                --i;
            }
        }
        while( i > 0)
        {
            ans.push_back(str1[i-1]);
            --i;
        }
        while( j > 0)
        {
            ans.push_back(str2[j-1]);
            --j;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }

public:
    string shortestCommonSupersequence(string str1, string str2) {

        int m = str1.length();
        int n = str2.length();

        return LCS(str1, str2, m ,n);
    }
};
var shortestCommonSupersequence = function(str1, str2) {
    const lcs = getLCS(str1, str2)
    
    let i = 0
    let j = 0

    let result = ''
    for (const c of lcs) {
        while(i < str1.length && str1[i] !== c) {
            result += str1[i]
            i++
        }
        while(j < str2.length && str2[j] !== c) {
            result += str2[j]
            j++
        }
        result += c
        i++
        j++
    }
    while(i < str1.length) {
        result += str1[i]
        i++
    }
    while(j < str2.length) {
        result += str2[j]
        j++
    }
    return result
};

function getLCS (a, b) {
    const t = new Array(a.length + 1).fill(0).map(() => new Array(b.length + 1).fill(0))
    
    for (let i = 1; i <= a.length; i++) {
        for (let j = 1; j <= b.length; j++) {
            if (a[i - 1] === b[j - 1]) {
                t[i][j] = 1 + t[i - 1][j - 1]
            } else {
                t[i][j] = Math.max(t[i - 1][j], t[i][j - 1])
            }
        }
    }
    
    let i = a.length
    let j = b.length
    let result = ''
    while(i > 0 && j > 0) {
        if (a[i-1] === b[j-1]) {
            result += a[i-1]
            i--
            j--
        } else {
            if (t[i-1][j] > t[i][j-1]) {
                i--
            } else {
                j--
            }
        }
    }
    return result.split('').reverse().join('')
}
Shortest Common Supersequence