[LeetCode] #29 Interleaving String

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    
    // state: dp[i][j] - whether s3.substring(0, i + j) is formed by s1.substring(0, i) and s2.substring(0, j)
    // function: dp[i][j] = (s3[i+j] == s1[i] && dp[i - 1][j]) ||
    //                      (s3[i+j] == s2[j] && dp[i][j - 1])
    // initialize: dp[0][0] = true
    //             dp[i][0] = s3[i] == s1[i] && dp[i - 1][0]
    // result: dp[s1.length()][s2.length()]
    
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        if (s1.length() + s2.length() < s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= s1.length() && i <= s3.length(); i++) {
            dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1][0]);
        }
        for (int j = 1; j <= s2.length() && j <= s3.length(); j++) {
            dp[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1) && dp[0][j - 1]);
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length() && i + j <= s3.length(); j++) {
                dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
            }
        }
        
        return dp[s1.length()][s2.length()];
    }
}