Problem Statement

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.  If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)

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.

Problem Link

Shortest Common Supersequence - LeetCode

Approach

Let X[0..m-1] and Y[0..n-1] be two strings and m and be respective
lengths.

if (m == 0) return n;
if (n == 0) return m;

// If last characters are same, then add 1 to result and
// recur for X[]
if (X[m-1] == Y[n-1])
    return 1 + SCS(X, Y, m-1, n-1);

// Else find shortest of following two
//  a) Remove last character from X and recur
//  b) Remove last character from Y and recur
else return 1 + min( SCS(X, Y, m-1, n), SCS(X, Y, m, n-1) );

Using the DP solution matrix, we can easily print shortest supersequence of two strings by following below steps –

We start from the bottom-right most cell of the matrix and
push characters in output string based on below rules-

 1. If the characters corresponding to current cell (i, j)
    in X and Y are same, then the character is part of shortest
    supersequence. We append it in output string and move
    diagonally to next cell (i.e. (i - 1, j - 1)).

 2. If the characters corresponding to current cell (i, j)
    in X and Y are different, we have two choices -

    If matrix[i - 1][j] > matrix[i][j - 1],
    we add character corresponding to current
    cell (i, j) in string Y in output string
    and move to the left cell i.e. (i, j - 1)
    else
    we add character corresponding to current
    cell (i, j) in string X in output string
    and move to the top cell i.e. (i - 1, j)

 3. If string Y reaches its end i.e. j = 0, we add remaining
    characters of string X in the output string
    else if string X reaches its end i.e. i = 0, we add
    remaining characters of string Y in the output string.

Note: Let s1 and s2 be two strings then, 
SCS(s1,s2) = length(s1) + length(s2) + LCS(s1,s2)

Code

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        
        int l1 = str1.size();
        int l2 = str2.size();
        
        vector<vector<int>> dp(l1+1,vector<int>(l2+1));
        
        for(int i=0;i<=l1;i++)
        {
            for(int j=0;j<=l2;j++)
            {
                if(!i)
                    dp[i][j] = j;
                
                else if(!j)
                    dp[i][j] = i;
                
                else if(str1[i-1]==str2[j-1])
                    dp[i][j] = 1+dp[i-1][j-1];
                
                else 
                    dp[i][j] = 1+ min(dp[i][j-1],dp[i-1][j]); 
            }
        }
        
        string scs;
        int i = l1, j =l2;
        
        while(i>0&&j>0)
        {
            if(str1[i-1]==str2[j-1])
            {
                scs.push_back(str1[i-1]);
                i--;j--;
            }
            
            else if(dp[i-1][j]<dp[i][j-1])
            {
                scs.push_back(str1[i-1]);
                i--;
            }
            else
            {
                scs.push_back(str2[j-1]);
                j--;
            }
        }
        while(i>0)
        {
            scs.push_back(str1[i-1]);
                i--;
        }
        while(j>0)
        {
            scs.push_back(str2[j-1]);
                j--;
        }
        
        reverse(scs.begin(),scs.end());
        return scs;
        
    }
};

Complexity Analysis

Time and Space Complexity of the above implementation is O(mn)