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.
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??
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
int isInterleaved(char* str1,char* str2,char* str3)
ReplyDelete{
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;
}
@ankit your approach is good but try finding out some pattern,to do it without using extra space...
ReplyDeletealgo :
ReplyDeletexnor(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??
@softy32 in case c has any other character then it is not interleaved...
ReplyDeletehmmm ok thn wt r ur comments for my logic..!!
ReplyDelete