algorithm - Dynamic Programming : The Zipper -

doing little practice on dynamic programming problems in preparation final , found problem stumped me.

zippers: given 3 strings, determine whether third string can formed combining characters in first 2 strings. first 2 strings can mixed arbitrarily, characters each must stay in original order in third string.

for example, consider forming "tcarete" "cat" , "tree": string a: c t string b: t r e e string c: t c r e t e

as can see, can form string c selecting first charcter of "tree", followed first 2 characters of "cat", followed second , third characters of "tree", followed last charcter of "cat" , "tree" respectively.

as second example, consider forming "catrtee" "cat" , "tree": string a: c t string b: t r e e string c: c t r t e e

the answer input 'yes'

output: output yes if , b can combined (zippered) string c. output no if , b cannot combined form c.

so want see if third string, c can formed , b. c t r t e e output no. biggest problem fact cat , tree both have letter t in it. can't run algorithm checks if 1 letter comes after other. on this?

because reviewing dynamic programming, should rather natural use problem.

now, let's think way:

1. for whole string c, if mixture of , b, first character must either first character of a, or first 1 in b;
2. now step further, first k characters in c, ka < k of them must a, , kb = k - ka of them must b.

from this, not hard find out algorithm use o(min(len(a), len(b))) space , use o(len(c) * min(len(a), len(b))) run.

hint: each step through c, of positions in must "on", while others "off". in end if character in both strings consumed, c can generated , b.