Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Shortest Common Supersequence

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

Shortest Common Supersequence



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #dynamicprogramming, #editdistance

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. 1 <= str1.length, str2.length <= 1000
  2. 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]
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #dynamicprogramming, editdistance, redo

Post navigation

LeetCode: Can Make Palindrome from Substring
LeetCode: Maximize Sum Of Array After K Negations

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.