// 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.