[LeetCode] 1092. Shortest Common Supersequence

Problem

https://leetcode.com/problems/shortest-common-supersequence/description/

Leetcode - Shortest Common Supersequence

Type - Dynamic programming, String, LCS(Longest Common Subsequence)

Difficulty - Hard

Approach & Solution

The worst case is string A+B or B+A(concatenation)

How can we shorten the length of the answer?

If we use common characters in str1 and str2 at once, no redundant characters are needed.

So, Longest Common Subsequence is needed.

data structures & variables:

• dp[i][j]: Length of LCS from between string(str1[0:i-1], str2[0:j-1])

• common: common LCS.

Let dp[i][j] is length of LCS from two substrings(str1[0:i-1], str2[0:j-1]).

Iterate 2D loops by doing:

• If str1[i-1] == str2[j-1], dp[i][j] = dp[i-1][j-1] + 1.

• Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Then, backtrack to recover LCS.

Initialize i = n, j = m, backtrack while i and j are positive.

• If str1[i-1] == str2[j-1], append str1[i-1].

• Else if dp[i-1][j] >= dp[i][j-1], reduce i by 1,

• Else, reduce j by 1. It means reduce boundary from greater one.

Since backtracking, LCS is given reversed.

So reverse the LCS.

Now, LCS is given, the last thing to do is to add exclusive characters in both string.

With two-pointer approach, set i = 0 and j = 0, i for str1, j for str2.

For each character ch in LCS:

• add str1[i] to answer and increment one while str1[i] ≠ ch. (add non-matching characters in

• add str2[j] to answer and increment one while str2[j] ≠ ch.

• now, str1[i] and str2[j] is ch. so, add ch and increment one for each i, j.

Finally, add suffixes: remaing str1[i:], str2[j:].

Complexity

Time Complexity: O(n*m) - Computing LSC with Bottom-Up DP.

• Plus, recovering LCS and constructing answer is O(n+m).

Space Complexity: O(n*m) - DP Matrix.

Code (C++ | Go)

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

        string common = "";
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                common.push_back(str1[i - 1]);
                i--; 
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        reverse(common.begin(), common.end());

        string ans = "";
        i = 0; j = 0;
        for (char c : common) {
            while (i < n && str1[i] != c) {
                ans.push_back(str1[i]);
                i++;
            }
            while (j < m && str2[j] != c) {
                ans.push_back(str2[j]);
                j++;
            }
            ans.push_back(c);
            i++;
            j++;
        }
        return ans + str1.substr(i) + str2.substr(j);
    }
};

func reverse(s string) string {
    n := len(s)
    b := []byte(s)
    for i := 0; i < n/2; i++ {
        b[i], b[n-i-1] = b[n-i-1], b[i]
    }
    return string(b)
}

func shortestCommonSupersequence(str1 string, str2 string) string {
    n := len(str1)
    m := len(str2)
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, m+1)
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if str1[i-1] == str2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }


    i := n
    j := m
    var common strings.Builder

    for i > 0 && j > 0 {
        if str1[i-1] == str2[j-1] {
            common.WriteByte(str1[i-1])
            i--
            j--
        } else if dp[i-1][j] >= dp[i][j-1] {
            i-- 
        } else {
            j--
        }
    }

    commonStr := common.String()
    reversed := reverse(commonStr)

    i = 0
    j = 0
    ans := ""
    for _, c := range reversed {
        for i < n && str1[i] != byte(c) {
            ans += string(str1[i])
            i++
        }
        for j < m && str2[j] != byte(c) {
            ans += string(str2[j])
            j++
        }
        ans += string(c)
        i++
        j++
    }

    for i < n {
        ans += string(str1[i])
        i++
    }

    for j < m {
        ans += string(str2[j])
        j++
    }

    return ans
}