Interleaving String

题目
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

答案

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] A = s1.toCharArray(), B = s2.toCharArray(), X = s3.toCharArray();
        int m = A.length, n = B.length, p = X.length;
        if(m + n != p) return false;
        /*
            Define f[s][i][j]: Is the first s letters in X formed by interleaving first i letters of A 
            and first j letters of B
            
            Can also define[i][j]: Is the first i+j letters in X formed by interleaving first i letters of A 
            and first j letters of B
        
            f[i][j] = (f[i][j - 1], if B[j - 1] == X[i + j - 1]) 
                      OR
                      (f[i - 1][j], if A[i - 1] == X[i + j - 1])
                    
        */
        boolean[][] f = new boolean[m + 1][n + 1];
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0) {
                    f[i][j] = true;
                    continue;
                }
                
                if(j > 0 && B[j - 1] == X[i + j - 1]) {
                    f[i][j] = f[i][j] || f[i][j - 1];
                }
                
                if(i > 0 && A[i - 1] == X[i + j - 1]) {
                    f[i][j] = f[i][j] || f[i - 1][j];
                }
            }
        }
        return f[m][n];
    }
}