Leetcode 1092: Shortest Common Supersequence

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"

Constraints:

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

Problem Analysis:

This problem is similar to solve longest common subsequence(LCS) problem. As the final string is str1 + str2-LCS. We can use dynamic programming to compute the LCS and then get the final string.

Assume dp[i][j] is the longest common substring length with str1 in [0..i-1] and str2 in [0..j-1]. We can get the dp values in two cases: first, when str1[i-1] = str2[j-1], then dp[i][j] = dp[i-1][j-1] + 1, otherwise, dp[i][j] = max(dp[i-1][j], dp[i-1][j]).

Then we can get the final string after delete the LCS characters.

Solution

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1));
        string res;
        for (int i = 1; i <= str1.size(); ++i) {
            for (int j = 1; j <= str2.size(); ++j) {
                if (str1[i - 1] == str2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        int i{(int)str1.size()}, j{(int)str2.size()};
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                res.push_back(str1[i - 1]);
                --i;
                --j;
            } else {
                if (dp[i - 1][j] > dp[i][j - 1]) {
                    res.push_back(str1[i - 1]);
                    --i;
                } else {
                    res.push_back(str2[j - 1]);
                    --j;
                }
            }
        }
        while (i > 0) {
            res.push_back(str1[i - 1]);
            --i;
        }
        while (j > 0) {
            res.push_back(str2[j - 1]);
            --j;
        }

        reverse(begin(res), end(res));
        return res;
    }
};

Time complexity is O(mn)

Space complexity is O(mn)