# Leetcode_1092. Shortest Common Supersequence
###### tags: `Leetcode` `Hard` `Longest Common Subsequence`

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.

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"

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string res="";
        int i=0,j=0;
        for(char c:LCS(str1,str2)){
            while(i<=str1.length()-1 && str1[i]!=c){
                res+=str1[i++];
            }
            while(j<= str2.length()-1 && str2[j]!=c){
                res+=str2[j++];
            }
            res+=c;
            i++;
            j++;
        }
        return res+str1.substr(i)+str2.substr(j);
    }
private:
    string LCS(string& A,string& B){
        int n=A.length(); // row
        int m=B.length(); // col
        vector<vector<string>> dp(n+1,vector<string>(m+1,""));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(A[i]==B[j]){
                    dp[i+1][j+1]=dp[i][j]+A[i];
                }else{
                    dp[i+1][j+1]=dp[i+1][j].length()>dp[i][j+1].length()?dp[i+1][j]:dp[i][j+1];
                }
            }
        }
        return dp[n][m];
    }
};

Reference (LCS): https://web.ntnu.edu.tw/~algo/Subsequence2.html