97. Interleaving String

https://leetcode.com/problems/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 lowercase English letters.

  • code
class Solution {
    public boolean dfs(String s1, String s2, String s3, int i1, int i2, int i3, int[][] memo){
        if (i1 == s1.length()) {
            return s2.substring(i2).equals(s3.substring(i3));
        }
        if (i2 == s2.length()) {
            return s1.substring(i1).equals(s3.substring(i3));
        }

        if (memo[i1][i2] >= 0){
            return memo[i1][i2] == 1 ? true : false;
        }
        
        if (s1.charAt(i1) == s3.charAt(i3) && dfs(s1, s2, s3, i1 + 1, i2, i3 +1, memo)){
            memo[i1][i2] = 1;
            return true;
        }
        if (s2.charAt(i2) == s3.charAt(i3) && dfs(s1, s2, s3, i1, i2 + 1, i3 + 1, memo)){
            memo[i1][i2] = 1;
            return true;
        }
        memo[i1][i2] = 0;
        return false;
    }
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        int[][] memo = new int[s1.length()][s2.length()];
        for (int i = 0; i < s1.length(); i++){
            for (int j = 0; j < s2.length(); j++){
                memo[i][j] = -1;
            }
        }
        return dfs(s1, s2, s3, 0, 0, 0, memo);
    }
}