Your iterative solution does not work in cases where both s1 and s2
have the next character in s3, but only choosing the s2 character next
will result in correct interleaving.
s1 = "ab"
s2 = "axb"
s3 = "axabb"
Your iterative solution will say that these are not interleaved, but
they really are.
Don
On May 20, 2:21 pm, immanuel kingston <kingston.imman...@gmail.com>
wrote:
> A Recursive solution:
>
> int interleaved(char *s1, char *s2, char *s3) {
> if (s1 == null && s2== null && s3==null) return 1;
> if (s3==null) return 0;
> if (s1 != null && *s1 == *s3) return interleaved(s1+1,s2,s3+1);
> else if (s2 != null && *s2 == *s3) return interleaved(s1, s2+1,s3+1);
> return 0;
>
> }
>
> Iterative solution:
> int interleaved(char *s1, char *s2, char *s3) {
> if (s1 == null && s2== null && s3==null) return 1;
> if (s3==null) return 0;
> while (*s3) {
> if (s1 != null && *s1 == *s3) {
> s1++;
> }
> else if (s2 != null && *s2 == *s3) {
> s2++;
> } else {
> return 0;
> }
> s3++;
> }
> return (s1 == null) && (s2 == null) && (s3 == null);
>
> }
>
> Thanks,
> Immanuel
>
> On Fri, May 20, 2011 at 8:42 PM, Don <dondod...@gmail.com> wrote:
> > This is the same algorithm as my previous solution. Both produce the
> > correct result, but this one does not have tail recursion, so it will
> > run faster.
>
> > bool interleaved2(char *s1, char *s2, char *s3)
> > {
> > while(1)
> > {
> > if (!s1[0] && !s2[0] && !s3[0]) return true;
> > if (s1[0] == s3[0])
> > {
> > if (s2[0] == s3[0])
> > {
> > if (interleaved2(s1+1, s2++,s3+1)) return true;
> > }
> > else ++s1;
> > }
> > else
> > {
> > if (s2[0] == s3[0]) ++s2;
> > else return false;
> > }
> > ++s3;
> > }
> > }
>
> > On May 19, 1:33 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote:
> > > Design an algorithm to find whether a given string is formed by the
> > > interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc
> > s3=
> > > aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find
> > whether
> > > s3 is formed from the interleaving of s1 and s2
>
> > > --
> > > *Piyush Sinha*
> > > *IIIT, Allahabad*
> > > *+91-8792136657*
> > > *+91-7483122727*
> > > *https://www.facebook.com/profile.php?id=100000655377926*
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
