# Interleaving String

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

```
//1D dynamic programming ie bottom up solution
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length(), l = s3.length();
if (m + n != l) return false;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int j = 1; j <= n; ++j) {
dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= m; ++i) {
dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
for (int j = 1; j <= n; ++j) {
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[n];
}
}
//2d dp
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n, l = len(s1), len(s2), len(s3)
if m + n != l:
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
return dp[m][n]
//recursion with memo (top down)
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n, l = len(s1), len(s2), len(s3)
if m + n != l:
return False
memo = {}
def helper(i: int, j: int, k: int) -> bool:
if k == l:
return True
if (i, j) in memo:
return memo[(i, j)]
ans = False
if i < m and s1[i] == s3[k]:
ans = ans or helper(i + 1, j, k + 1)
if j < n and s2[j] == s3[k]:
ans = ans or helper(i, j + 1, k + 1)
memo[(i, j)] = ans
return ans
return helper(0, 0, 0)
```

## Related Problems

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return *the maximum number of envelopes you can Russian doll (i.e., put one inside the other)*.

**Note:** You cannot rotate an envelope.

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?