// Returns true if string s3 is s1 interleaved with s2.
// The function is iterative when possible, but uses a recursive
// call when both s1 and s2 match the next character in s3.
// Note that this function is not intended to be called directly. It
is called by Interleaved().
bool interleaved2(char *s1, char *s2, char *s3)
{
while(1)
{
// End case is when all three strings are empty
if (!s1[0] && !s2[0] && !s3[0]) return true;
if (s1[0] == s3[0])
{
if (s2[0] == s3[0])
{
// Tries both using s1 and s2 next. The recursive call uses
s1,
// and the postincrement of s2 uses s2 iteratively.
if (interleaved2(s1+1, s2++,s3+1)) return true;
}
// s1 is the only match
else ++s1;
}
else
{
// s2 is the only match
if (s2[0] == s3[0]) ++s2;
// Neither s1 nor s2 match the next character in s3 so the
strings are not interleaved
else return false;
}
// Move on to the next character in s3
++s3;
}
}
bool Interleaved(char *s1, char *s2, char *s3)
{
// Frequency counts
int count1[256] = {0};
int count2[256] = {0};
int i,j;
// Count the number of occurances of each character in s1 and s2
for(i = 0; s1[i]; ++i)
++count1[s1[i]];
for(j = 0; s2[j]; ++j)
++count1[s2[j]];
j += i;
// Next count the number of occurances of each character in s3
for(i = 0; s3[i]; ++i)
++count2[s3[i]];
// If the total number of characters in s3 is not s1+s2, interleaved
is false
if (i != j) return false;
// If s3 is s1 interleaved with s2, these counts must be equal
for(i = 1; i < 128; ++i)
if (count1[i] != count2[i])
return false;
// Call the function to do the real work.
return interleaved2(s1,s2,s3);
}
On Aug 31, 8:43 am, Navneet <[email protected]> wrote:
> Suppose the two strings are ab and cd.
>
> The possible strings formed by interleaving these two are
> abcd, acbd, acdb , cabd etc..
>
> On Aug 31, 5:23 pm, sukran dhawan <[email protected]> wrote:
>
> > what do u mean by interleaving ?
>
> > On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta <[email protected]>wrote:
>
> > > The important thing to notice here is that relative order of
> > > characters is important and hence you should not look for just count
> > > char based approaches.
>
> > > On Wed, Aug 31, 2011 at 11:20 AM, Navneet Gupta <[email protected]>
> > > wrote:
> > > > Given two strings S1 and S2, Find whether another string S3 can formed
> > > > by interleaving S1 and S2. Only constant space.
>
> > > > --
> > > > Regards,
> > > > Navneet
>
> > > --
--
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.
