Interleaving.java

package Algorithms;
public class Interleaving {
    public static void main(String[] strs) {
        System.out.println(isInterleave("a", "b", "ab"));
        if ('a' >= 'd') {
            System.out.println("tre");
        }
        int a = 'c';
        int b = 'a';
        
        char c = Character.toLowerCase('9');
        return;
    }
    
    public static boolean isInterleave(String s1, String s2, String s3) {
        // f[i][j] means that  from 0-i in S1 and from 0-j in S2 compose to S3(i+j)
        // f[i][j]:
        // 1. s1.i == s3.(i+j) && s1(i - 1) + s2(j) compase s3(i + j  - 1)
        // || s2.j == s3.(i+j) && s1(i) + s2(j - 1) compase s3(i + j  - 1)
        // init: 
        // f[0][0] = true;
        // when i = 0, f[i][j] = f[i][j - 1] && s2(j) == s3(i+j)
        // when j = 0, f[i][j] = f[i - 1][j] && s1(i) == s3(i+j)
        if (s3 == null) {
            return false;
        }
        
        if (s2 == null && s1 == null) {
            return false;
        }
        
        if ((s1 == null || s1.length() == 0) && s2 != null) {
            return s2.equals(s3);
        } else if ((s2 == null || s2.length() == 0) && s1 != null) {
            return s1.equals(s3);
        }
        
        boolean[][] match = new boolean[s1.length() + 1][s2.length() + 1];
        
        match[0][0] = true;
        for (int j = 1; j <= s2.length(); j++) {
            match[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1) && match[0][j - 1]); 
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            match[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1) && match[i - 1][0]); 
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                // f[i][j]:
                // 1. s1.i == s3.(i+j) && s1(i - 1) + s2(j) compase s3(i + j  - 1)
                // || s2.j == s3.(i+j) && s1(i) + s2(j - 1) compase s3(i + j  - 1)
                match[i][j] = false;
                match[i][j] |= match[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                match[i][j] |= match[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
            }
        }
        
        return match[s1.length()][s2.length()];
    }
}