I have a solution which should work. Only problem here is worst case
time complexity is exponential. Though real world chances of that
happening is very very low.
bool Interleaved(char *s1, char *s2, char *s3)
{
if(s1 == NULL && s2 == NULL && s3 == NULL)
{
//All strings exhausted, hence return true
return true;
}
else if((s1 != NULL || s2 != NULL) && s3 == NULL)
{
//Either of s1 or s2 is not exhausted, but s3 is
exhausted
return false;
}
else if(s1 == NULL)
{
//Remaining s2 characters should be same as remaining
s3 characters
if(CheckSameTillNull(s2,s3))
return true;
else
return false;
}
else if(s2 == NULL)
{
//Remaining s1 characters should be same as remaining
s3 characters
if(CheckSameTillNull(s1,s3))
return true;
else
return false;
}
else
{
if((*s1 == *s3) && (*s2 == *s3))
return Interleaved(++s1,s2,++s3) ||
Interleaved(s1,++s2,++s3);
else if(*s1 == *s3)
return Interleaved(++s1,s2,++s3);
else if(*s2 == *s3)
return Interleaved(s1,++s2,++s3);
else
//No matching character in either s1 or s2 for
character in s3
return false;
}
}
On Sep 1, 4:50 pm, bharatkumar bagana <[email protected]>
wrote:
> bool interleave(string s1,string s3)
> {
> char *str1=(char*)s1.c_str();
> char *str3=(char*)s3.c_str();
> int pos=-1;
> for(int i=0;i<strlen(str1);i++)
> {
> if(pos<findPosition(str1[i],str3))
> {
> pos=findPosition(str1[i],str3);
> }
> else {flag=1; break;}
> }
> if(flag==1)
> print NOT........}
>
> Do the same for string2 also ...
> This works only for non duplicated strings ....
>
>
>
>
>
>
>
>
>
> On Thu, Sep 1, 2011 at 5:19 AM, vikas <[email protected]> wrote:
> > @ above, a third string is used, s3 which is strlen(s2)+ strlen(s1)
> > and thus in O(n) space
>
> > I guess qs calls out for O(1) space.
>
> > besides , if we have O(n) space , this question simply reduces to
> > finding the number of permutation of string s1+s2
>
> > I doubt we can do it in O(1) space, any idea guys ???
>
> > On Aug 31, 7:00 pm, Don <[email protected]> wrote:
> > > // 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.
>
> --
>
> **Please do not print this e-mail until urgent requirement. Go Green!!
> Save Papers <=> Save Trees
> *BharatKumar Bagana*
> **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
> *
> Mobile +91 8056127652*
> <[email protected]>
--
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.
