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