So I have this question:
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. Example would be
X = AND Y = THE Z = ATHNED -> A N D TH E
So this would return true. I've seen solution to this using Dyanimc Programming, but I came up with just a purely iterative algorithm that runs in O(|Z|), but I'm guessing there must be something wrong with it since all the solutions I've seen all use either memoization or DP.
Basic psuedocode for my solution (I omit some obvious base cases):
solution(X,Y,Z): i = j = 0 for(k=0 to |Z|): if(either i or j out of bounds): return false if(Z[k] == A[i]): i++ elif(Z[k] == B[j]): j++ else: return false return true
Basically this just runs down string Z and marks off whichever string it came from, and when a character doesnt match either, it cant be an interleaved string.
Can someone pick this apart and tell me what's wrong and why I have to use DP?