97. Interleaving String

Dynamic programming, dfs

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length()!=s1.length()+s2.length()) return false;
        // key: as long as s3 is consisent of characters in s1 and s2 (1 to 1 match),
        // there is |n-m|<=1
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();

        // memo[i][j] represent substring (length==i) of s1, and substring (length==j) 
        boolean[][] memo = new boolean[s1.length()+1][s2.length()+1];
        memo[0][0] = true;
        return checkInterleave(c1, c2, c3, 0, 0, memo);
    }
    
    private boolean checkInterleave(char[] c1, char[] c2, char[] c3, int index1, int index2, boolean[][] memo){
        if(index1==c1.length && index2==c2.length) return memo[index1][index2];
        
        // assume that memo[index1][index2] has been checked
        // the next is to check memo[index1+1][index2] and memo[index1][index2+1]
        boolean bool1 = false;
        boolean bool2 = false;
        if(memo[index1][index2]){
            if (index1<c1.length && !memo[index1+1][index2]){
                memo[index1+1][index2] = c3[index1+index2]==c1[index1];
                bool1 = checkInterleave(c1, c2, c3, index1+1, index2, memo);
            } 
            if(index2<c2.length && !memo[index1][index2+1]){
                memo[index1][index2+1] = c3[index1+index2]==c2[index2];
                bool2 = checkInterleave(c1, c2, c3, index1, index2+1, memo);
            }
        }
        return bool1 || bool2;
    }
}

DFS // Timeout

class Solution {
    boolean result = false;
    
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s3.length() != s1.length()+s2.length()) return false;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        
        checkInterleaving(c1, c2, c3, 0, 0, 0);
        checkInterleaving(c2, c1, c3, 0, 0, 0);
        return result;
    }
    // make sure this is always true: index3 = index1+index2+1 
    private void checkInterleaving(char[] c1, char[] c2, char[] c3, int index1, int index2, int index3){
        if(index3 == c3.length || result){
            result = true;
            return;
        }
        
        // always make c1 to be the array to match, index1 as the index;
        while (index3<c3.length && index1<c1.length && c3[index3]==c1[index1]){
            checkInterleaving(c2, c1, c3, index2, index1+1, index3+1);
            index3++;
            index1++;
        }
    }
}