Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Shortest Common Super-sequence

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 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
A

Anonymous

· 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
A

Anonymous

· 4 years ago

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

Reading Progress

0%

Vote for new content