## 97. 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 lower-case English letters.

## Rust Solution

``````struct Solution;
use std::collections::HashMap;

impl Solution {
fn is_interleave(s1: String, s2: String, s3: String) -> bool {
let n1 = s1.len();
let n2 = s2.len();
let n3 = s3.len();
let s1: Vec<char> = s1.chars().collect();
let s2: Vec<char> = s2.chars().collect();
let s3: Vec<char> = s3.chars().collect();
let mut memo: HashMap<(usize, usize, usize), bool> = HashMap::new();
Self::dp(0, 0, 0, &mut memo, &s1, &s2, &s3, n1, n2, n3)
}

fn dp(
i: usize,
j: usize,
k: usize,
memo: &mut HashMap<(usize, usize, usize), bool>,
s1: &[char],
s2: &[char],
s3: &[char],
n1: usize,
n2: usize,
n3: usize,
) -> bool {
if i == n1 && j == n2 && k == n3 {
true
} else {
if let Some(&res) = memo.get(&(i, j, k)) {
return res;
}
let res = (i < n1
&& k < n3
&& s1[i] == s3[k]
&& Self::dp(i + 1, j, k + 1, memo, s1, s2, s3, n1, n2, n3))
|| (j < n2
&& k < n3
&& s2[j] == s3[k]
&& Self::dp(i, j + 1, k + 1, memo, s1, s2, s3, n1, n2, n3));
memo.insert((i, j, k), res);
res
}
}
}

#[test]
fn test() {
let s1 = "aabcc".to_string();
let s2 = "dbbca".to_string();