Simple tabular DP (C++)


#1
int Solution::isInterleave(string A, string B, string C) {
int n = A.length(), m = B.length();
int dp[n+1][m+1];
memset(dp,0,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
    if(A[i-1]==C[i-1])
        dp[i][0]=1;
    else
        break;
}
for(int i=1;i<=m;i++){
    if(B[i-1]==C[i-1])
        dp[0][i]=1;
    else
        break;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(A[i-1]==C[i+j-1]||B[j-1]==C[i+j-1])
            dp[i][j] = dp[i-1][j]||dp[i][j-1];
        else
            dp[i][j]=0;
    }
}
return dp[n][m];
}