# \[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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/dfs/97-jiao-cuo-zi-fu-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.