4] Suppose you are given three strings of characters: X, Y ,and Z,where
|X| = n,
|Y | = m,and |Z| = n + m. Z is said to be a shuﬄe of X and Y iﬀ Z can be
formed by interleaving the characters from X and Y in a way that
maintains the
left-to-right ordering of the characters from each string.
(a) Show that cchocohilaptes is a shuﬄe of chocolate and chips, but
chocochilatspe
is not.
(b) Give an eﬃcient dynamic-programming algorithm that determines
whether Z
is a shuﬄe of X and Y . Hint: the values of the dynamic programming
matrix
you construct should be Boolean, not numeric.