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])
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.