O(n^3) solution java


#1
public class Solution {
    public int isInterleave(String A, String B, String C) {
        int a = A.length() , b = B.length() , c = C.length();
        if(c > a+b) return 0;
        int[][][] dp = new int[a+1][b+1][c+1];
        for(int i = 1 ; i<=a;i++)
        for(int j = 1;j<=b;j++)
        for(int k = 1;k<=c;k++) {
            if(A.charAt(i-1) == C.charAt(k-1)){
                if(B.charAt(j-1) == C.charAt(k-1)){
                    dp[i][j][k] = 1+ Math.max(dp[i-1][j][k-1] , dp[i][j-1][k-1]);
                } else {
                     dp[i][j][k] = 1+ Math.max(dp[i-1][j][k-1] , dp[i][j-1][k]);
                }
            } else if(B.charAt(j-1) == C.charAt(k-1)){
                if(A.charAt(i-1) == C.charAt(k-1)){
                    dp[i][j][k] = 1+ Math.max(dp[i][j-1][k-1],dp[i-1][j][k-1]);
                } else {
                    dp[i][j][k] = 1+Math.max(dp[i][j-1][k-1], dp[i-1][j][k]);
                }
            } else {
                dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i][j-1][k]);
            }
        }
        if(dp[a][b][c] == c-1) return 1; else return 0;
    }
}