Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;


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|cite|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

Your Answer


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

Browse other questions tagged or ask your own question.