Yahoo Interview Question
Software Engineer / Developersumm..just struck me - why do we need to get into dp? Will this work (a very simple algo)
first check length of bigger string = len(s1) + len(s2)
pick up the first string and look for its letters (in the same order) in the bigger string - if all the letters are consumed, proceed - replace the letters thus consumed with say a space
now for the remaining letters check if the letters of the second string are consumed, => if yes, true
even in case of repition, it should work because the order would be preserved regardless of whether the letter was taken from 1st string or 2nd.
consider -
s1 - abcd
s2 - bccld
abbccdcld
checking for letters of s1:
the frst a,b,c,d crossed out
=> __b_c_cld
checking for the letters of 2nd string => consumed - yes! :D
O(n + m)
{{
can you explain how the order would be O(m+n)
because I think for canceling out the elements from bigger string you have to search the smaller string whether the current character is in the string or not.
}}
Oh I don't think that would be necessary, mate!
See...you need not search the whole string if you don't find a letter. you will be searching for the first small string in the large string. And in case you don't find a character of the smaller string in the larger one, going ahead, you stop there and say "It ain't an interleaving".
Say, if the big string above was abbkkdkld, you would find a, then b, and then you won't find c of the str1 after ab.... That's it. you stop there...
{{
if string comprised of ASCII characters only then
first check strlen(C) == strlen(A) + strlen(B)
make an array F[256]
initialize all Elements of F with 0.
then scan string A and for i=0 to strlen(A) do F[A[i]]++
then scan string B and for i=0 to strlen(B) do F[B[i]]++
then scan string C and for i=0 to strlen(C) do F[C[i]]--
then check whether all elements are zero or not !! DONE
I guess there exists a pretty simple linear complexity solution.
Take 3 variables to store indexes of strings a,b,c
Iterate all chars of c using cindex. If char matches current char frm a, move a and c indeces
If char matches current char from b, move b and c indexes
However if char doesn't match any of cur a,b current chars then c isn't interleaved
However if all chars of c were matched with some a,b char then c is interleaved
// helper : is A a subsequence of C
bool isSubsequence(char *a, char *c){
int i=0,j=0;
while(a[j] && c[i]){
if(a[j] == c[i]) { j++;}
i++;
}
if(a[j]) return false;
}
bool isInterleaved(char *a, char *b, char *c){
return isSubsequence(a,c) && isSubsequence(b,c) && (strlen(a)+strlen(b)==strlen(c));
}
// helper : is A a subsequence of C
bool isSubsequence(char *a, char *c){
int i=0,j=0;
while(a[j] && c[i]){
if(a[j] == c[i]) { j++;}
i++;
}
return a[j] ? false : true;
}
bool isInterleaved(char *a, char *b, char *c){
return isSubsequence(a,c) && isSubsequence(b,c) && (strlen(a)+strlen(b)==strlen(c));
}
if the elements are different it can be done in O(n+m). Otherwise it would be O(n^2) using dynamic programming.
I would like you to observe that to define the state in dynamic programming(in this case) by just i1,i2. i3 is not required for memoization since always i3=i1+i2;
- Anonymous September 13, 2010Since there are n^2 states and each state takes O(1) time the overall time complexity will be O(n^2)