WAP to design an efficient algorithm to find whether String s3 is formed from the interleaving of String s1 and String s2

Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not.
s1= aabccabc
s2= dbbabc
s3= aabdbbccababcc

If I am Correct a Similer Iterative Approahc can be written as

bool test(A,B,C)
{
i=j=k=0;
while(k < C.size()) { if(i < A.size() && C[k]==A[i]) {i++,k++; } else if(j < B.size() && C[k]==B[j]) { j++,k++; } else return false } return (i == A.size() && j == B.size()); } Similer Recursive Apparoahc in Which Interviewer Show More Interest bool interleaved(char *s1, char *s2, char *s3) { // Base case, all strings are empty return (!s1[0] && !s2[0] && !s3[0]) || // First character of s1 is next in s3 (s1[0] && (s1[0] == s3[0]) && interleaved(s1+1,s2,s3+1)) || // First character of s2 is next in s3 (s2[0] && (s2[0] == s3[0]) && interleaved(s1,s2+1,s3+1)); } No Doubt This Problem Requires DP (Top-Down memozation will be Best )Approach & I had Solved It Using the Same. Below is one of The Possible Approach. I found A Good Discussion Here AlgoGeek


TC O(N) length of Bigger String thats S3 Need to Check
SC O(1)
Run Here http://ideone.com/n6RLc