Google interview : Interleaved string

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.

Comments

  1. int isInterleaved(char* str1,char* str2,char* str3)
    {
    int alphabets[26]={0};
    int len1=strlen(str1);
    int len2=strlen(str2);
    for(int i=0;i<len1;i++)
    {
    alphabets[str1[i]-'a']++;
    }
    for(int i=0;i<len2;i++)
    {
    alphabets[str2[i]-'a']++;
    }

    for(int i=0;i<strlen(str3);i++)
    {
    alphabets[str3[i]-'a']--;
    }

    for(int i=0;i<26;i++)
    {
    if(alphabets[i]!=0)return 0;
    }
    return 1;





    }

    ReplyDelete
  2. @ankit your approach is good but try finding out some pattern,to do it without using extra space...

    ReplyDelete
  3. algo :
    xnor(C,A+B)
    this function will return the number of similiar characters(say static sim, increment sim if similar character is found in the pattern) in C and A+B,right Shift A+B by one and continue till the length of C, (you can call xnor recursively) , then do the same by taking the A+B to the ptr+(length(C)-lenght(A+B))and left shifting by one continue till the length of C, (you can call xnor recursively)..
    in the calling programm if sim == length(A+B) => Yes interleaved, other wise no.
    one question is C's length = lengh (A+B) or it can have other characters as well??

    ReplyDelete
  4. @softy32 in case c has any other character then it is not interleaved...

    ReplyDelete
  5. hmmm ok thn wt r ur comments for my logic..!!

    ReplyDelete

Post a Comment

Popular posts from this blog