A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. For example, the string BANANA ANANAS is a shue of the strings BANANA and ANANAS in several different ways.

BANANAANANAS BANANAANANAS BANANANANA

Similarly, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING:

PROGRAMMING PROGRAMMING

Describe and analyze an efficient algorithm to determine, given throe strings A1 [1...m], B [1...n] and C[1...m+n], whether C is a shuffle of A and B.

Shuffle (A[1..m], B[1..n], C[1..m+n]):

Shuf[0, 0] ← True

for j ← 1 to n

Shuf[0, j] ← Shuf[0, j − 1] ∧ (B[j] = C[j])

for i ← 1 to n

Shuf[i, 0] ← Shuf[i − 1, 0] ∧ (A[i] = B[i])

for j ← 1 to n

Shuf[i, j] ← False

if A[i] = C[i + j]

Shuf[i, j] ← Shuf[i, j] ∨ Shuf[i − 1, j]

if B[i] = C[i + j]

Shuf[i, j] ← Shuf[i, j] ∨ Shuf[i, j − 1]

return Shuf[m, n]

The algorithm runs in O(mn) time.

i do not get the question.

do not use any of these common illegal characters/symbols:

# pound

% percent

& ampersand

{ left curly bracket

} right curly bracket

\ back slash

< left angle bracket

> right angle bracket

* asterisk

? question mark

/ forward slash

  blank spaces

$ dollar sign

! exclamation point

' single quotes

" double quotes

: colon

@ at sign