Interleaving String

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

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lower-case English letters.

Solution:

class Solution {
    Boolean[][][] dp;
    
    public boolean isInterleave(String s1, String s2, String s3) {
        int a = s1.length(), b = s2.length(), c = s3.length();
        if (a + b != c) return false;
        dp = new Boolean[a][b][c];
        return helper(s1, 0, s2, 0, s3, 0);
    }
    
    private boolean helper(String s1, int i, String s2, int j, String s3, int k) {
        // System.out.println(i + ", " + j + ", " + k);
        if (i == s1.length()) {
            return s2.substring(j).equals(s3.substring(k));
        } else if (j == s2.length()) {
            return s1.substring(i).equals(s3.substring(k));
        }
        if (dp[i][j][k] != null) return dp[i][j][k];
        char a = s1.charAt(i);
        char b = s2.charAt(j);
        char c = s3.charAt(k);
        if (a == c) {
            if (helper(s1, i + 1, s2, j, s3, k + 1)) {
                return dp[i][j][k] = true;
            }
        }
        if (b == c) {
            if (helper(s1, i, s2, j + 1, s3, k + 1)) {
                return dp[i][j][k] = true;
            }
        }
        return dp[i][j][k] = false;
    }
}