Interleaving String | Leetcode

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:
s1 = "aabcc",
s2 = "dbbca",

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

---

Solution: This is a good practice problem for 2D dynamic programming.

First check the lengths of the strings to make sure they match before we start doing anything.

For the algorithm and formula, it is probably better to read the code directly.

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

        for (int i = 0; i < s2.length() && s2.charAt(i) == s3.charAt(i); i++) {
            m[0][i + 1] = true;
        }
        
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                m[i + 1][j + 1] =
                        (m[i][j + 1] && s1.charAt(i) == s3.charAt(i + j + 1)) ||
                        (m[i + 1][j] && s2.charAt(j) == s3.charAt(i + j + 1));
            }
        }
        return m[s1.length()][s2.length()];
    }
}