There are some things which could be done to make the program run
faster in some cases.
For example, either version of my solution above will take a very long
time to determine that these inputs are not interleaved:
s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
s3 =
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
Adding code at the beginning to be sure that s3 has the same number of
instances of each character as s1 and s2 would be quick and would make
that case much faster.
Don
On May 20, 10:12 am, 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.
