Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Shortest Common Super-sequence

Problem Statement

Given two sequences 's1' and 's2', write a method to find the length of the shortest sequence which has 's1' and 's2' as subsequences.

Example 2:

Input: s1: "abcf" s2:"bdcf" 
Output: 5
Explanation: The shortest common super-sequence (SCS) is "abdcf".

Example 2:

Input: s1: "dynamic" s2:"programming" 
Output: 15
Explanation: The SCS is "dynprogrammicng".

Constraints:

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of lowercase English letters.

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Shan

· 4 years ago

The counting version of this problem is easy, whereas the leetcode problem ( https://leetcode.com/problems/shortest-common-supersequence/ ) requires building the actual string. Using the DP table could help, can you provide the additional steps to build the output?

Side note: To reuse previous solutions, s1.length() + s2.length() - len(lcs_count) will also yield the expected solution. i.e. the LCS for Example 1 (btw mislabeled as Example 2) is "bcf" therefore 4 + 4 - 3 = 5. This also applies to Example 2: 7 + 11 - 3 because the LCS is "ami".

Show 1 reply
S

Shan

· 4 years ago

time and space for top down is same as bottom up, this should be clearly stated

N

navdeepsharmatu

· 2 years ago

If s1 : aebd

s2 : cdfe

o/p should be 6 as shortest common supersequence is : aebdcf

but algo returns 7.

can someone help where i am wrong ?

Show 1 reply