Interleaving String

Problem

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

Example

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

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

Code - Java

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
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();

        boolean[][] match = new boolean[c1.length + 1][c2.length + 1];

        if (c1.length + c2.length != c3.length) return false;

        match[0][0] = true;
        for (int i = 1; i <= c3.length; i++) {
            for (int j = 0; j <= i; j++) {
                int k = i - j;
                if (j > c1.length || k > c2.length) continue;
                if (j - 1 >= 0 && match[j - 1][k] && c1[j - 1] == c3[i - 1]) {
                    match[j][k] = true;
                }

                if (k - 1 >= 0 && match[j][k - 1] && c2[k - 1] == c3[i - 1]) {
                    match[j][k] = true;
                }
            }
        }
        return match[c1.length][c2.length];
    }
}