[algogeeks] Re: String Problem

[Navneet]

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 
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 {
>   if(pos   {
>     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  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  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  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  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 r

Re: [algogeeks] Re: String Problem

[bharatkumar bagana]

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 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  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  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  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
*
Mobile +91 8056127652*


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

[algogeeks] Re: String Problem

[vikas]

@ 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  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  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  wrote:
>
> > > what do u mean by interleaving ?
>
> > > On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta 
> > > 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 
> > > > 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.

[algogeeks] Re: String Problem

[Don]

// 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  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  wrote:
>
> > what do u mean by interleaving ?
>
> > On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta 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 
> > > 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.

[algogeeks] Re: String Problem

[Navneet]

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  wrote:
> what do u mean by interleaving ?
>
> On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta 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 
> > wrote:
> > > Given two strings S1 and S2, Find whether another string S3 can formed
> > > by interleaving S1 and S2. Only constant space.
>
> > > --
> > > Regards,
> > > Navneet
>
> > --
> > 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.

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

Re: [algogeeks] Re: String Problem

[sukran dhawan]

what do u mean by interleaving ?

On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta 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 
> wrote:
> > Given two strings S1 and S2, Find whether another string S3 can formed
> > by interleaving S1 and S2. Only constant space.
> >
> > --
> > Regards,
> > Navneet
> >
>
>
>
> --
> 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.
>
>

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

[algogeeks] Re: String Problem

[Navneet Gupta]

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  wrote:
> Given two strings S1 and S2, Find whether another string S3 can formed
> by interleaving S1 and S2. Only constant space.
>
> --
> Regards,
> Navneet
>



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

Re: [algogeeks] Re: String Problem

[Amir hossein Shahriari]

@amit: does the order of characters in Ssmall have to be the same in Sbig?

On 6/27/10, amit  wrote:
> @ above can u plzz explain how to do it using LCS...
>
> I think u r finding the LCS and then backtracking to keep into account
> the first and the last characters of the LCS in the Longer
> stringCorrect me if I am wrong...
>
> On Jun 27, 9:57 am, Anand  wrote:
>> http://codepad.org/NDAeIpxR
>> Here is code for it
>>
>> On Sat, Jun 26, 2010 at 9:54 PM, Anand  wrote:
>> > you can use Longest common subsequence algorithm to solve it.
>>
>> > On Sat, Jun 26, 2010 at 4:04 PM, amit  wrote:
>>
>> >> You r given a large string of characters lets call it Sbig. Then there
>> >> is a small set of characters lets call it Ssmall. You have to find
>> >> smallest substring of Sbig which contains all characters in Ssmall.
>>
>> >> For example you are given Sbig = "hello what are you doing"
>> >> Ssmall= "eo"
>>
>> >> answer is "ello"
>> >> 24
>>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> >> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algoge...@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.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.

[algogeeks] Re: String Problem

[amit]

@ above can u plzz explain how to do it using LCS...

I think u r finding the LCS and then backtracking to keep into account
the first and the last characters of the LCS in the Longer
stringCorrect me if I am wrong...

On Jun 27, 9:57 am, Anand  wrote:
> http://codepad.org/NDAeIpxR
> Here is code for it
>
> On Sat, Jun 26, 2010 at 9:54 PM, Anand  wrote:
> > you can use Longest common subsequence algorithm to solve it.
>
> > On Sat, Jun 26, 2010 at 4:04 PM, amit  wrote:
>
> >> You r given a large string of characters lets call it Sbig. Then there
> >> is a small set of characters lets call it Ssmall. You have to find
> >> smallest substring of Sbig which contains all characters in Ssmall.
>
> >> For example you are given Sbig = "hello what are you doing"
> >> Ssmall= "eo"
>
> >> answer is "ello"
> >> 24
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@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.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.