[ASSIGNMENT] Shortest common supersequence

Question

Given X and Y two strings code a program finding their shortest commpn supersequence C so that X and Y can be obtained from C only by supressing letters and C's size is as low as possible. Ie abcdf + bde => abcdef or abcdfe but not efdcba (you can recreate the two strings just by suppressing letters)

Test (the result can be different in some cases but needs to be as small)

("abcbdab","bdcaba"),"abdcabdab
("123456","abcdef"),"123456abcdef" (or any variation like 1a2b3c4def56")
("gatctga","atct"),"

Answer 1

https://code.sololearn.com/cQoT884QqU8c/?ref=app

Answer 2

Here is my version
https://code.sololearn.com/c2w7NzrdxQc8

Answer 3

I believe (UPD: I'm sure now) that this should work as a solution for such task:

https://code.sololearn.com/cjAavVl4mZrC/?ref=app

It is based on the previous one for the related task (https://www.sololearn.com/Discuss/1254598/?ref=app):

https://code.sololearn.com/cpsKMKAAHnS3/?ref=app

It demonstrate the same complexity by time and memory, however I assume that a better one based on dynamic programming with memoization can be found for both tasks...

Answer 4

Still struggling on the dynamic programming version, but here is my oneliner recursive solution. https://code.sololearn.com/cWl0szMe2gAZ/#py

Answer 5

VcC my program does solve your test cases, if you don't enter two strings. Just hit submit at the prompt without typing anything.

Answer 6

@JPM7 You can also try the second one from @VcC challenges on about this topic:
https://www.sololearn.com/Discuss/1254598/?ref=app
@VcC Will we also get a longer example to test the performance of solutions?

Answer 7

~ swim ~ You should be able to make X and Y out of C just by removing characters

Answer 8

Not saying this is not an interesting challenge but not the one i proposed :-)

Answer 9

@JPM7 Not exactly about the topic, but good reading anyway.
The first one can be applied for 3SUM challenge: https://www.sololearn.com/learn/5461/
If I remember it well @VcC has such solution published.

Answer 10

Since nobody else didn't want to demonstrate the solution based on dynamic programming with memoization approach, I have done it by my own:

https://code.sololearn.com/cBB5qa7mEtXz/?ref=app

It is based on the previous one for the related task (https://www.sololearn.com/Discuss/1254598/?ref=app). See this code for realization of this approach for the previous task:

https://code.sololearn.com/c7W8OV49STkF/?ref=app

Its time and memory complexities should be both equal to O(N*M), where M and N - lengths of input strings.
However, I'm not the expert in a field, so feel free to test it and inform me about any bugs that you have met!

Answer 11

Nevfy my code includes a dynamic programming solution
https://code.sololearn.com/csH8yT3oNfBJ/?ref=app

Answer 12

@VcC Oh, I see. I think you added it after I saw it the last time, so I didn't mention this fact. Sorry.
Nevertheless, this is a code, which solves your previous challenge (longest common substring), but not this one. However, it is easy to convert. ;-)

Answer 13

John Wells JPM7 Can you use the suggested test cases ?

Answer 14

Louis No see what i told to ~swim

Answer 15

~ swim ~ youe solution does not seem to solve the problem i proposed...

Answer 16

Letters look to be in the wrong order.

Answer 17

Note: fast methods to do this are used to process genetic codes and recognize common patterns in genes.