DP O(N^2) Solution


#1
int Solution::isInterleave(string A, string B, string C) {
    int a = A.length(), b = B.length(), c = C.length();
    bool dp[c + 1][a + 1];
    memset(dp, false, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= c; i++) {
        for (int j = max(0, i - b); j <= a; j++) {
            int k = i - j;
            if (k > 0 && dp[i - 1][j] && C[i - 1] == B[k - 1])
                dp[i][j] = 1;
            if (j > 0 && dp[i - 1][j - 1] && C[i - 1] == A[j - 1])
                dp[i][j] = 1;
        }
    }
    for (int i = 0; i <= a; i++)
        if (dp[c][i])
            return 1;
    return 0;
}