Solution without dp, O(a+b)

int a=A.length();
int b=B.length();
int c=C.length();
if((a+b)!=c) return 0;
int i=0,j=0,k=0;
int start_i=0;
int start_j=INT_MAX;
int start_k=INT_MAX;
while(i<a || j<b){
if(A[i]==C[k] && B[j]==C[k]){
start_i=i;
start_j=j+1;
start_k=k+1;
i++;
k++;
}
else if(A[i]==C[k]){
i++;
k++;
}
else if(B[j]==C[k]){
j++;
k++;
}
else{
if(start_j==INT_MAX){
return 0;
}
else{
i=start_i;
j=start_j;
k=start_k;
start_j=INT_MAX;
}
}
}
return 1;

}

Click here to start solving coding interview questions