88. Interleaving String

Let dp[i][j] mean the first i characters of s1 and the first j characters of s2 can interleave to form the first i+j characters of s3. A cell is reachable if the matching character of s3 came from s1 (extending dp[i-1][j]) or from s2 (extending dp[i][j-1]).

Idea

Define dp[i][j] = can s1[:i] and s2[:j] interleave into s3[:i+j]? The last character of s3[:i+j] (index i+j-1) must have come from either s1 or s2:

• From s1: s1[i-1] == s3[i+j-1] and dp[i-1][j] was reachable.
• From s2: s2[j-1] == s3[i+j-1] and dp[i][j-1] was reachable.

dp[0][0] is True (empty interleaves to empty). If total lengths don't match, it's immediately False.

Algorithm

1. If len(s1) + len(s2) != len(s3), return False.
2. dp[0][0] = True. Fill the grid: set dp[i][j] true if either the s1-source or s2-source condition holds.
3. Return dp[m][n].

Worked example: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

The dp grid reaches dp[5][5] = True, so true.

Complexity

• Time: O(m·n).
• Space: O(m·n) (reducible to O(n)).

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }
}