> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/dfs/97-jiao-cuo-zi-fu-chuan.md).

# \[97]\[困难]\[动态规划]\[DFS]\[BFS] 交错字符串

## 题目描述

[97. 交错字符串](https://leetcode-cn.com/problems/interleaving-string/)

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

```
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
```

示例 2:

```
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
```

## 解题思路

### 动态规划

容易想到递归的思路, 如果`s3`是由`s1`, `s2`交错组成的, 那么`s3 - 1`肯定是由`s1 - 1`, `s2`或`s1`, `s2 - 1`交错组成的. 由此得到动态规划的状态为长串是否由两个短串交错组成的, 相应的状态转移方程也得到了.

使用一个二维数组来记录状态. 两个维度长度分别是`s1`和`s2`字符串的长度, `dp[i][j]`代表是否是由`s1[:i+1]`和`s2[:j+1]`交错组成的.

然后考虑边际. 首先加上限制条件, `s1`, `s2`的长度之和必须等于`s3`的长度, 否则肯定不匹配, 不加也会使得推断过程中索引越界. 满足长度限制后, 要考虑边际中`s3`的前缀完全是由`s1`或`s2`中某一个的前缀组成的, 即另一个字符串没有任何元素参数, 这就要考虑空串交叉的情况, 因此`dp`的两个维度大小都要加上1, 考虑空串.

首先`dp[0][0]=True`, 这是空串肯定是由两个空串交错组成的. 然后考虑`dp[i][0]`和`dp[0][j]`的边际状态. 明显应该分别遍历`s1`, `s2`, 将前缀匹配的位置对应`dp`的位置置为`True`, 直到遇到第一个不匹配的字符, 包括此位置在内的, 之后的所有边际位置都不匹配, 保持`False`.

整体代码如下. 时间复杂度和空间复杂度都为$$O(N^2)$$. 空间复杂度可以利用滚动数组优化到$$O(N)$$, 这是因为我们求`dp[i][j]`只会用到`dp[i-1][j]`和`dp[i][j-1]`, 即只会使用上一行或上一列的状态, 按行或按列滚动即可.

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m, l = len(s1), len(s2), len(s3)
        if n + m != l:
            return False
        dp = [[False] * (m + 1) for _ in range(n + 1)]

        # 初始化状态矩阵的初始条件, 即边际状态
        dp[0][0] = True
        for i in range(n):
            if s1[i] == s3[i]:
                dp[i + 1][0] = True
            else:
                break
        for i in range(m):
            if s2[i] == s3[i]:
                dp[0][i + 1] = True
            else:
                break

        for i in range(n):
            for j in range(m):
                if (s3[i + j + 1] == s1[i] and dp[i][j + 1]) or (s3[i + j + 1] == s2[j] and dp[i + 1][j]):
                    dp[i + 1][j + 1] = True
        return dp[-1][-1]
```

### DFS + 记忆化

既然可以递归, 那么DFS思路肯定也是可以的. 当`s3[:i+j]`与`s1[:i]`, `s2[:j]`匹配时, 我们接下来要搜索的就是`s3[:i+j+1]`与`s1[:i+]`, `s2[:j]`以及`s3[:i+j+1]`与`s1[:i]`, `s2[:j+1]`是否匹配, 然后继续向下递归. 停止条件是`i`和`j`都超出了边界, 说明整体都是OK的.

可以预见到, 在此DFS过程中肯定会遇到大量的重复计算, 如果有多条路可以找到`s3[:i+j]`与`s1[:i]`, `s2[:j]`这个位置, 则这个位置之后相同的搜索, 肯定会重复多次. 因此有必要加入记忆化, 判断此位置是否已经到达过, 如果到达过, 就可以剪枝了.

记忆化可以用二维数组, 或者用哈希表来实现.

代码如下:

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m, l = len(s1), len(s2), len(s3)
        if n + m != l:
            return False

        seen = dict()

        def dfs(i, j):
            if (i, j) in seen:
                return seen[(i, j)]

            res = (i < n and s1[i] == s3[i + j] and dfs(i + 1, j)) or (j < m and s2[j] == s3[i + j] and dfs(i, j + 1)) or (i + j == l)
            seen[(i, j)] = res
            return res

        return dfs(0, 0)
```

### BFS + 记忆化

其实此题中BFS与DFS思路很接近, 只是一个用递归, 一个用栈, 利用栈的特性.

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m, l = len(s1), len(s2), len(s3)
        if n + m != l:
            return False

        seen = set()
        stack = [(0, 0)]

        while stack:
            indices = stack.pop()
            if indices in seen:
                continue
            seen.add(indices)

            i, j = indices
            if i == n and j == m:
                return True

            if i < n and s1[i] == s3[i + j]:
                stack.append((i + 1, j))
            if j < m and s2[j] == s3[i + j]:
                stack.append((i, j + 1))

        return False
```

## 参考资料

* [DFS缓存+DP动态规划 简洁清晰（Python3）](https://leetcode-cn.com/problems/interleaving-string/solution/dfshuan-cun-jian-ji-qing-xi-python3-by-dz-lee/)
* [「手画图解」DFS回溯 及其优化](https://leetcode-cn.com/problems/interleaving-string/solution/shou-hua-tu-jie-dfshui-su-dfsji-yi-hua-by-hyj8/)
* [动态规划、DFS、BFS全齐活](https://leetcode-cn.com/problems/interleaving-string/solution/dong-tai-gui-hua-dfs-bfsquan-qi-huo-by-java_lee/)