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 <bagana.bharatku...@gmail.com> 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 <vikas.rastogi2...@gmail.com> 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 <dondod...@gmail.com> 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 <navneetn...@gmail.com> 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 <sukrandha...@gmail.com> wrote: > > > > > > what do u mean by interleaving ? > > > > > > On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta < > > navneetn...@gmail.com>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 < > > navneetn...@gmail.com> > > > > > > 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 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. > > -- > > **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* > <bagana.bharatku...@gmail.com> -- 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.