Solution: Interleaving String
Tags: algorithms, javascript, java, python
Published: 2021-06-03 04:25:43

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/interleaving-string/discuss/1248268).*

---

#### [Leetcode Problem #97 (*Medium*): Interleaving String](https://leetcode.com/problems/interleaving-string/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output:| true
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg)
>
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.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

If we consider a matrix with indices (**i**) for **s1** on one axis and indices (**j**) for **s2** on the other, then a successful **s3** can be considered a path moving from the top left to the bottom right. At each point, we either move downward (**i++**) by choosing the next letter from **s1** or rightward (**j++**) by choosing the next letter from **s2**.

All that remains, then, is to see which vertices are possible given **s3**, and which ones are not. To do that, we can use a **dynamic programming** (**DP**) approach. Normally, we would establish a matrix as described above, along with a buffer row/column at the start of the matrix to provide space for previous row/column validation checks for the leading edges of our iteration. An additional row/column at the end of the matrix is also needed, since our final checks will occur only _after_ the strings are completed.

We can reduce the **space complexity** of this solution from **O(N * M)** to just **O(M)**, however, if rather than building a full DP matrix, we instead only keep the current rows of the matrix (**dp**) in memory, reiterating through it for each row. The left value will already have been calculated, and the up value will not yet have been overwritten in the current cell.

We should also remember to fill dp[1] with a **true** (or **1**) value, representing a valid vertex at the starting position of our iteration path.

From there, we can iterate through the rows, building upon previously completed entries to check the validity of the current cell. If the cell "above" (the not-yet-overwritten dp[i] represents the same index from the row above) is valid (**true** or **1**) and the corresponding characters of **s1** and **s3** match, then the current cell is valid. Similarly, if the cell to the left is valid and the corresponding characters of **s2** and **s3** match, then the current cell is valid.

Once we've finished iterating through **i** and **j**, a valid value in the last cell of **dp** will indicate that a valid path exists that matches **s3**, so we can just **return** the contents of that cell.

 - _**Time Complexity: O(N * M)** where **N** is the length of **s1** and **M** is the length of **s2**_
 - _**Space Complexity: O(M)** for **dp**_


---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var isInterleave = function(s1, s2, s3) {
    let n = s1.length + 2, m = s2.length + 2
    if (n + m - 4 !== s3.length) return false
    let dp = new Uint8Array(m)
    dp[1] = 1
    for (let i = 1; i < n; i++)
        for (let j = 1; j < m; j++) {
            let up = dp[j] && s1[i-2] === s3[j+i-3],
                left = dp[j-1] && s2[j-2] === s3[j+i-3]
            dp[j] = up || left
        }
    return dp[m-1]
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1) + 2, len(s2) + 2
        if n + m - 4 != len(s3): return False
        dp = [0] * m
        dp[1] = 1
        for i in range(1, n):
            for j in range(1, m):
                up = dp[j] and (i < 2 or s1[i-2] == s3[j+i-3])
                left = dp[j-1] and (j < 2 or s2[j-2] == s3[j+i-3])
                dp[j] = up or left
        return dp[-1]
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length() + 2, m = s2.length() + 2;
        char[] sc1 = s1.toCharArray(), sc2 = s2.toCharArray(), sc3 = s3.toCharArray();
        if (n + m - 4 != s3.length()) return false;
        boolean[] dp = new boolean[m];
        dp[1] = true;
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                boolean up = dp[j] && (i < 2 || sc1[i-2] == sc3[j+i-3]),
                    left =dp[j-1] && (j < 2 || sc2[j-2] == sc3[j+i-3]);
                dp[j] = up || left;
            }
        return dp[m-1];
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length() + 2, m = s2.length() + 2;
        if (n + m - 4 != s3.length()) return false;
        vector<bool> dp(m);
        dp[1] = true;
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                bool up = dp[j] && (i < 2 || s1[i-2] == s3[j+i-3]),
                    left = dp[j-1] && (j < 2 || s2[j-2] == s3[j+i-3]);
               dp[j] = up || left;
            }
        return dp[m-1];
    }
};
```