problem : KOL1510 Problem - CodeChef
my solution : Qyaw2Y - Online C++0x Compiler & Debugging Tool - Ideone.com
I am trying to find the shortest common supersequence for all the strings… whats wrong in this approach?? i am getting wrong answer
problem : KOL1510 Problem - CodeChef
my solution : Qyaw2Y - Online C++0x Compiler & Debugging Tool - Ideone.com
I am trying to find the shortest common supersequence for all the strings… whats wrong in this approach?? i am getting wrong answer
Input:
1 3 B G GB
Correct output is GB
.
Your code constructs BG
from the first 2 and then BGB
from BG
and GB
, which is incorrect.
so if i sort the strings according to size and construct the solution using the largest words first… will it work??
It did’nt… well can u suggest any modification i need to do in my solution?? or should i go with the editorial?? thanks in advance
An approach like this will not work for sure. That’s because the shortest common supersequence problem for more than two strings is NP-Complete (according to Wikipedia). So you should take a look at the editorial