LeetCode: Shortest Common Supersequence

Posted on September 2, 2019July 26, 2020 by braindenny

Shortest Common Supersequence

Similar Problems:

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.

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/shortest-common-supersequence
// Basic Ideas: dynamic programming + edit distance
// Complexity: Time O(n*m*n), Space O(n*(n+m))
func shortestCommonSupersequence(str1 string, str2 string) string {
    l := make([]string, len(str2)+1)
    // Compare "" with s2[j...]
    for j:=len(str2)-1; j>=0; j-- {
        l[j] = string(str2[j])+l[j+1]
    }
    str := ""
    // Compare s1[i...] with s2[j...]
    for i:=len(str1)-1; i>=0; i-- {
        str = string(str1[i])+str
        l2 := make([]string, len(str2)+1)
        l2[len(str2)] = str
        for j:=len(str2)-1; j>=0; j-- {
            if str1[i] == str2[j] {
                l2[j] = string(str1[i]) + l[j+1]
            } else {
                if len(l[j]) < len(l2[j+1]) {
                    l2[j] = string(str1[i])+l[j]
                } else {
                    l2[j] = string(str2[j])+l2[j+1]
                }
            }
        }
        copy(l, l2)
    }
    return l[0]
}

Post Views: 0