@ 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
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;istrlen(str1);i++)
{
if(posfindPosition(str1[i],str3))
{
pos=findPosition(str1[i],str3);
}
else {flag=1; break;}
}
if(flag==1)
print NOT
}
Do
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
what do u mean by interleaving ?
On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta navneetn...@gmail.comwrote:
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
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
// 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
@ 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 anandut2...@gmail.com wrote:
