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 anywherefrom T) results in the string S.)

Example 1:

Input: str1 = "abac", str2 = "cab"

Output: "cabac"

Explanation:

str1 = "abac" is a substring of "cabac" because we can delete the first "c".

str2 = "cab" is a substring of "cabac" because we can delete the last "ac".

The answer provided is the shortest such string that satisfies these properties.

Note:

1. 1 <= str1.length, str2.length <= 1000
2. str1 and str2 consist of lowercase English letters.

题意：构造一个字符串，使得其子序列同时包含有 str1 和 str2，要求这个字符串在满足要求情况下长度最短

题解：找出 str1 和 str2 的最长公共子序列，剩余不在最长公共子序列中的字符拼接到这个最长公共子序列中。

class Solution {

public:

    string shortestCommonSupersequence(string str1, string str2) {

        string res = "";

        int len1 = str1.size(), len2 = str2.size();

        int dp[len1 + 5][len2 + 5];

        memset(dp, 0, sizeof(dp));

        int i, j;

        for (i = 1; i <= len1; i++){

            for (j = 1; j <= len2; j++){

                if (str1[i - 1] == str2[j - 1])    dp[i][j] = dp[i - 1][j - 1] + 1;

                else    dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j];

            }

        }

        i = len1, j = len2;

        string common = "";

        while (dp[i][j]){

            if (dp[i][j] == dp[i - 1][j])   i--;

            else if (dp[i][j] == dp[i][j - 1])  j--;

            else    common += str1[i - 1], i--, j--;

        }

        reverse(common.begin(), common.end());

        int len3 = common.size();

        i = 0, j = 0;

        for (int k = 0; k < len3; k++){

            while (i < len1 && str1[i] != common[k]){

                res += str1[i++];

            }

            while (j < len2 && str2[j] != common[k]){

                res += str2[j++];

            }

            res += common[k];

            i++;

            j++;

        }

        while (i < len1){

            res += str1[i++];

        }

        while (j < len2){

            res += str2[j++];

        }

        return res;

    }

};