Interleaving String

Given three strings: s1, s2, s3, determine whether s3is formed by the interleaving of s1 and s2.

Have you met this question in a real interview? 

Yes

Example

For s1 = "aabcc", s2 = "dbbca"

• When s3 = "aadbbcbcac", return true.
• When s3 = "aadbbbaccc", return false.

Challenge

O(n2) time or better

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