10.7

(a) Why “cchocohilaptes” is a shuffle, but “chocochilatspe” is not
Take  X = chocolate  and  Y = chips. Scan the candidate shuffle from left-to-right and decide, at each position, whether the next unused character of X or of Y is taken:

Z : c c h o c o h i l a p t e s ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ X : c h o c o l a t e ↑ ↑ ↑ ↑ ↑ ↑ ↑ Y : c h i p s ↑ ↑ ↑ ↑

The order inside each source string is preserved, so “cchocohilaptes” is a legal shuffle. Trying the same scan for “chocochilatspe” fails when the prefix “choco” is read: both source strings expect different next letters (l from X and c from Y), so the ordering constraint is broken; hence that string is not a shuffle.

(b) Dynamic-programming algorithm
Let DP[i][j] be a Boolean that is true iff the prefix Z[1‥i+j] is a shuffle of X[1‥i] and Y[1‥j]. Base row/column handle the cases where only one string contributes: DP[0][0] = true
DP[i][0] = DP[i-1][0] ∧ (X[i] = Z[i])
DP[0][j] = DP[0][j-1] ∧ (Y[j] = Z[j])
Transition for every i ≥ 1, j ≥ 1:
DP[i][j] = (DP[i-1][j] ∧ X[i] = Z[i+j]) ∨ (DP[i][j-1] ∧ Y[j] = Z[i+j])
The answer is DP[n][m]. Time complexity is Θ(nm), space is the same but can be reduced to Θ(min(n,m)) by keeping only one row (or column) at a time.

Back to Chapter 10