*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #97 (*Medium*): Interleaving String

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given strings

`s1`

,`s2`

, and`s3`

, find whether`s3`

is formed by aninterleavingof`s1`

and`s2`

.An

interleavingof two strings`s`

and`t`

is a configuration where they are divided intonon-emptysubstrings 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:*

*Examples:*

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

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

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

####
*Constraints:*

*Constraints:*

`0 <= s1.length, s2.length <= 100`

`0 <= s3.length <= 200`

`s1`

,`s2`

, and`s3`

consist of lowercase English letters.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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];
}
};
```

## Discussion (3)

I think I have an O(N) solution, where N is the length of s3.

I might be missing corner cases, or have misunderstood the task 😁

Unfortunately, this code always picks from

lastif the current letter matchess3. But what if the current letter of bothlastandothermatch? You would need to try both options to see if either works.Consider

s1 = "ba",s2 = "bc",s3 = "bcba". Your solution would pick the"b"froms1but then would return afalsebecause its only options would be the"a"froms1or the"b"froms2to match the"c"froms3. But clearly, we can take the entire"bc"froms2and then the entire"ba"froms1to matchs3, so the answer should betrue.We could use a

recursiveorstackapproach at this point to try the multiple branches, but then we'd start overlapping cases and redoing the same subproblems, which will take too long. This is the issue thatdynamic programminghelps to solve, by storing the results of these subproblems in a way that allows them to be accessed again, rather than resolving.Ah! Thanks for insight.