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

Example

Solution: Dynamic Programming
isInterleave[i][j] = if first i chars of s1 and first j chars of s2 is interleave of first i+j chars of s3
isInterleave[i][j] = isInterleave[i – 1][j] && s1.charAt(i – 1) == s3.charAt(i + j – 1))
|| (isInterleave[i][j – 1] && s2.charAt(j – 1) == s3.charAt(i + j – 1))

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null
            || s1.length() + s2.length() != s3.length()) {
        return false;
    }
    //isInterleave[i][j] = if first i chars of s1 and first j chars of s2
    //is interleave of first i+j chars of s3
    boolean[][] isInterleave = new boolean[s1.length() + 1][s2.length() + 1];
    isInterleave[0][0] = true;
    for (int i = 1; i <= s1.length(); i++) {
        isInterleave[i][0] = isInterleave[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    }
    for (int j = 1; j <= s2.length(); j++) {
        isInterleave[0][j] = isInterleave[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
    }
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            isInterleave[i][j] = (isInterleave[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                                 || (isInterleave[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
    return isInterleave[s1.length()][s2.length()];
}

Share