Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to develop an algorithm to check whether a string s3 is interleaving of another strings s1 and s2.

Say s1="abc" and s2="abe", then possible interleavings are ababce, ababec or abcabe. I solved it something like this :

A: string1, B: string2 and C: interleaving of A and B

bool isInterLeaved(int i,int j,int k,char A[],char B[],char C[])
{

if(!A[i] && !B[j] && !C[k]) return 1;

Note : I will do memoization to store the state, I have pasted just snippet to show my intent of the algorithm.

if(!A[i] || !B[j] || !C[k])
return 0;

bool x=0,y=0;

if(C[k]==A[i])
x=isInterLeaved(i+1,j,k+1,A,B,C);

if(!x)
{
if(C[k]==B[j])
{
y=isInterLeaved(i,j+1,k+1,A,B,C); }
}
return (x||y);
}

As there are a*b states, order is O(a*b) where a = Size of string A and b = size of String B.

I wanted to know if this can be done in better way. If characters in both A and B are mutually exclusive then it can be achieved in O(n) easily, but here characters can be same as well, but still I believe there can be better ways of doing this. If anyone have any ideas do let me know.

share|improve this question
    
$O(ab)$ is already far better than the naive $O(\binom{a+b}{a})$ algorithm. (But it seems that you need some memoization in addition to what you have written, before you can actually claim that $O(ab)$ complexity). –  Henning Makholm Sep 28 '12 at 19:20
    
I will do memoization of states, above code is just for showing my way of solving the issue. –  user43005 Sep 29 '12 at 5:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.