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 <[email protected]> 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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
