algorithm - Find the minimal lexographical string formed by merging two strings -

suppose given 2 strings s1 , s2(both lowercase). have 2 find minimal lexographic string can formed merging 2 strings.

at beginning , looks prettty simple merge of mergesort algorithm. let see can go wrong.

s1: zyy

s2: zy

now if perform merge on these 2 must decide z pick equal, if pick z of s2 first string formed be:

zyzyy

if pick z of s1 first, string formed be:

zyyzy correct.

as can see merge of mergesort can lead wrong answer.

here's example:

s1:zyy

s2:zyb

now correct answer zybzyy got if pick z of s2 first.

there plenty of other cases in simple merge fail. question is there standard algorithm out there used perform merge such output.

you use dynamic programming. in f[x][y] store minimal lexicographical string such you've taken x charecters first string s1 , y characters second s2. can calculate f in bottom-top manner using update:

f[x][y] = min(f[x-1][y] + s1[x], f[x][y-1] + s2[y]) \\ '+' here represents                                                     \\ concatenation of                                                      \\ string , character 

you start f[0][0] = "" (empty string).

for efficiency can store strings in f references. is, can store in f objects

class stringref {     stringref prev;     char c; } 

to extract string have @ f[x][y] follow references. udapate point either f[x-1][y] or f[x][y-1] depending on update step says.