# 97. Interleaving String

[**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:**![](https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg)

```
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.

**Follow up:** Could you solve it using only `O(s2.length)` additional memory space?

**My Solutions:**

方法1： Recursion with memoization

i, j, k分别代表s1,s2,s3三个字符串的起始地址\
（1）s3的首字母是来自s1吗？如果是，可以拆解为s1的 i+1 与 s2的j 与s3的Interleaving String子问题。\
（2）s3的首字母是来自s2吗？如果是，可以拆解为s2的 j+1 与 s2的j 与s3的Interleaving String子问题。\
以上2个条件成立一个，表示结果成立。\
Base Case: 如果k超过了s3的length，表示s3是空串，返回TRUE\
\
加一个二维矩阵来记录结果值，这样可以减少不必要的重复计算。

* Time complexity: O(m\*n), where m is the length of s1 and n is the length of s2. That's a consequence of the fact that each `(i, j)` is computed only once.
* Space complexity: O(m\*n) to keep the double array `memo`.

```
class Solution {
    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()];
        // initialize all the number to -1
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                memo[i][j] = -1;
            }
        }
        return getMemory(s1, 0, s2, 0, s3, 0, memo);
    }
    
    public boolean getMemory(String s1, int i, String s2, int j, String s3, int k, int[][] memo) {
        // if i is at the end of s1
        if (i == s1.length()) {
            return s2.substring(j).equals(s3.substring(k));
        }
        // if j is at the end of s2
        if (j == s2.length()) {
            return s1.substring(i).equals(s3.substring(k));
        }
        if (memo[i][j] >= 0) {
            return memo[i][j] == 1 ? true : false;
        }
        boolean ans = false;
        if (
            (s3.charAt(k) == s1.charAt(i) && getMemory(s1, i + 1, s2, j, s3, k + 1, memo))
                || (s3.charAt(k) == s2.charAt(j) && getMemory(s1, i, s2, j + 1, s3, k + 1, memo))
        ) {
            ans = true;
        }
        memo[i][j] = ans ? 1 : 0;
        return ans;
    }
}
```

方法2：Using 2D Dynamic Programming

D\[i]\[j]: 定义为s1 (前i个字符) s2(前j个字符) s3(i+j 个字符) 是不是交叉字符&#x20;

* s1 s3 首字母相同，继续查i -1 与 i + j -1 是否isInterleave
* s2 s3 首字母相同，继续查j -1 与 i + j -1 是否isInterleave

递推公式： (s1.i == s3.(i+j) && D\[i-1]\[j]) || (s2.j == s3.(i+j) && D\[i]\[j - 1])&#x20;

* Time complexity: O(m\*n). dp array of size m\*n is filled.
* Space complexity: O(m\*n). 2D dp of size (m+1)\*(n+1) is required.

```
boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
        if (i == 0 && j == 0) {
            dp[i][j] = true;
        } else if (i == 0) {
            dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
        } else if (j == 0) {
            dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
        } else {
            dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) 
            || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
}
return dp[s1.length()][s2.length()];
```

方法3：Using 1D Dynamic Programming

Use only 1D dp array to store the results of the prefixes of the strings processed so far. Instead of maintaining a 2D array, maintain a 1D array only and update the array's element dp\[i] when needed using dp\[i-1] and the previous value of dp\[i].

```
boolean dp[] = new boolean[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
        if (i == 0 && j == 0) {
            dp[j] = true;
        } else if (i == 0) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
        } else if (j == 0) {
            dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
        } else {
            dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
}
return dp[s2.length()];
```
