Easiest and Simple O(C.length()) solution CPP


#1

int Solution::isInterleave(string A, string B, string C) {
int m , n , o;

m = A.size();
n = B.size();
o = C.size();

if((m+n) != o){
    return 0;
}
int p = 0, q = 0 , r = 0;
while(p < m && q < n){
    if(A[p] == C[r]){
        p++;
        r++;
    }
    else if(B[q] == C[r]){
        q++;
        r++;
    }
    else{ 
        r--;
        
        if(B[q] == C[r]){// This is because we have given first priority to A 
            r++;           // therefore checking for B also
            q++;
            p--;
            continue;
        }
        
        return 0;
    }
}

while(p < m){
    if(A[p] == C[r]){
        p++;
        r++;
    }
    else
        return 0;
    }
}
while(q < n){
    if(B[q] == C[r]){
        q++;
        r++;
    }
    else{
        return 0;
    }
}

return 1;

}


#2

“aabcc”
“dbbca”
“aadbbcbcac”
this test case