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 
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):

   i = j = 0
   for(k=0 to |Z|):
      if(either i or j out of bounds):
         return false
      if(Z[k] == A[i]):
      elif(Z[k] == B[j]):
         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?


closed as unclear what you're asking by David Richerby, Raphael Apr 3 '16 at 8:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is a request to verify or debug a piece of code. $\endgroup$ – David Richerby Apr 3 '16 at 8:05
  • 1
    $\begingroup$ Plus, the problem is not even specified. There is only the definition of the shuffle, but not the task. $\endgroup$ – Raphael Apr 3 '16 at 8:28
  • $\begingroup$ "Can someone pick this apart" -- that's your job, really, at least to start with. Have you tried proving correctness? Have you tried it on some examples; is it incorrect? $\endgroup$ – Raphael Apr 3 '16 at 8:29
  • $\begingroup$ "whichever string it came from" you are assuming the alphabets are disjoint, which makes the task easy. $\endgroup$ – Hendrik Jan Apr 3 '16 at 9:15

Consider the following counter example

Let $A = aa$

Let $B = aab$

Let $Z = aabaa$

Your code will return false while the answer is true.

This is because you are giving preference to matching $A$ before matching $B$. There is no property of the problem that says that it is optimal to match all characters to $A$ before $B$ in case the character can be in both $A$ and $B$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.