LeetCode 题目 97：动态规划、递归到广度优先搜索BFS 实现交错字符串

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

输入格式

• s1, s2, s3：三个字符串。

输出格式

• 返回布尔值，表示 s3 是否可以由 s1 和 s2 交错组成。

示例

示例 1

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: True
1
2

示例 2

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: False
1
2

---

方法一：动态规划

解题步骤

1. 定义状态：dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否形成 s3 的前 i+j 个字符。
2. 状态转移：
   • 如果当前字符来自 s1，则 dp[i][j] = dp[i-1][j] 且 s1[i-1] 必须等于 s3[i+j-1]。
   • 如果当前字符来自 s2，则 dp[i][j] = dp[i][j-1] 且 s2[j-1] 必须等于 s3[i+j-1]。

完整的规范代码

def isInterleave(s1, s2, s3):
    """
    动态规划判断 s3 是否为 s1 和 s2 交错组成
    :param s1: str, 第一个字符串
    :param s2: str, 第二个字符串
    :param s3: str, 第三个字符串
    :return: bool, 是否交错组成
    """
    l1, l2, l3 = len(s1), len(s2), len(s3)
    if l1 + l2 != l3:
        return False
    
    dp = [[False] * (l2 + 1) for _ in range(l1 + 1)]
    dp[0][0] = True
    for i in range(1, l1 + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    for j in range(1, l2 + 1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]

    for i in range(1, l1 + 1):
        for j in range(1, l2 + 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[l1][l2]

# 示例调用
print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))  # 输出: True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

算法分析

• 时间复杂度：(O(m * n))，其中 m 和 n 分别为 s1 和 s2 的长度。
• 空间复杂度：(O(m * n))，用于存储动态规划表。

算法图解

使用动态规划来具体解释并展示如何验证字符串 s1 = "aabcc", s2 = "dbbca", 和 s3 = "aadbbcbcac" 是否是交错字符串的过程。这里将详细构建对应的动态规划表格，并用 ASCII 图表来形象化展示。

表格准备

• 行代表 s1 的前缀。
• 列代表 s2 的前缀。
• 单元格 (i, j) 表示使用 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。

初始化

• dp[0][0] 自然为 True（两个空字符串总是可以组成另一个空字符串）。
• 第一行和第一列需要单独初始化，因为它们代表其中一个字符串是空的情况。

动态规划过程

我们将遍历 s3 并逐个填充 dp 表的值，检查是否能通过添加 s1 或 s2 的字符来匹配 s3 的对应位置。

ASCII 表的表示

DP Table:
          ""   d   b   b   c   a
      "" [T]  [F]  [F]  [F]  [F]  [F]
      a  [F]  [F]  [F]  [F]  [F]  [F]
      a  [F]  [F]  [F]  [F]  [F]  [F]
      b  [F]  [F]  [F]  [F]  [F]  [F]
      c  [F]  [F]  [F]  [F]  [F]  [F]
      c  [F]  [F]  [F]  [F]  [F]  [F]
1
2
3
4
5
6
7
8

递推逻辑的 ASCII 说明

以填充 dp[1][1] 为例：

dp[1][1] = (dp[0][1] and s1[0] == s3[1]) or (dp[1][0] and s2[0] == s3[1])
         = (False and 'a' == 'a') or (False and 'd' == 'a')  // 给出示例中的字符比较
         = False or False
         = False
1
2
3
4

完整的 DP 表填充过程

为了简明起见，我们仅展示关键步骤，下面是 s3 完整匹配的 DP 表最后几行状态：

          ""   d   b   b   c   a
      "" [T]  [F]  [F]  [F]  [F]  [F]
      a  [F]  [F]  [F]  [F]  [F]  [F]
      a  [F]  [F]  [F]  [F]  [F]  [F]
      b  [F]  [F]  [T]  [T]  [F]  [F]
      c  [F]  [F]  [F]  [T]  [T]  [F]
      c  [F]  [F]  [F]  [F]  [T]  [T]
1
2
3
4
5
6
7

这个 ASCII 表揭示了通过动态规划如何逐步确认 s3 是否能由 s1 和 s2 交错组成。整个过程的可视化有助于理解交错字符串问题的动态规划解决方案的复杂性和执行流程。

方法二：递归（带记忆化）

解题步骤

1. 递归定义：递归判断是否可能交错组成 s3。
2. 记忆化存储：使用哈希表避免重复计算相同的子问题。

完整的规范代码

def isInterleave(s1, s2, s3):
    memo = {}
    def dfs(i, j, k):
        if (i, j) in memo:
            return memo[(i, j)]
        if k == len(s3):
            return i == len(s1) and j == len(s2)
        valid = (i < len(s1) and s1[i] == s3[k] and dfs(i+1, j, k+1)) or \
                (j < len(s2) and s2[j] == s3[k] and dfs(i, j+1, k+1))
        memo[(i, j)] = valid
        return valid

    return dfs(0, 0, 0)

# 示例调用
print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))  # 输出: True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

算法分析

• 时间复杂度：(O(m * n))，利用记忆化减少了重复计算。
• 空间复杂度：(O(m * n))，递归栈和记忆化存储的开销。

方法三：广度优先搜索 (BFS)

解题步骤

1. 使用队列：利用队列进行广度优先搜索，每次从队列中取出节点，并尝试向前推进 s1 或 s2。
2. 状态检查：检查当前的字符匹配情况，并决定是否继续推进。

完整的规范代码

from collections import deque

def isInterleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    queue = deque([(0, 0)])
    visited = set((0, 0))
    while queue:
        i, j = queue.popleft()
        if i + j == len(s3):
            return True
        if i < len(s1) and s1[i] == s3[i + j] and (i + 1, j) not in visited:
            queue.append((i + 1, j))
            visited.add((i + 1, j))
        if j < len(s2) and s2[j] == s3[i + j] and (i, j + 1) not in visited:
            queue.append((i, j + 1))
            visited.add((i, j + 1))
    return False

# 示例调用
print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))  # 输出: True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法分析

• 时间复杂度：(O(m * n))，可能需要遍历所有可能的状态。
• 空间复杂度：(O(m * n))，用于存储访问状态的队列和集合。

算法图解

我们可以通过 ASCII 图解来形象化展示其搜索过程。以下是如何使用 BFS 方法来判断字符串 s1 = "aabcc", s2 = "dbbca", 和 s3 = "aadbbcbcac" 是否交错组成的一个步骤示例。

在这个方法中，我们将使用一个队列来追踪当前访问的节点位置 (i, j)，其中 i 是 s1 的索引，j 是 s2 的索引。这样，每个元素的状态可以表示为它是否能由之前的状态推进而来。

BFS 的队列操作过程

我们初始化队列与访问集合来确保不重复处理相同的状态。队列中的每个元素都代表一个待验证的状态，即能否通过当前索引组合 (i, j) 交错组成 s3 的 i+j 部分。

ASCII 表的表示

下面是一个简化的 ASCII 表示，说明了状态的扩展过程：

Queue Operations:
Initial Queue State: [(0, 0)]  // Start from the empty prefixes of s1 and s2

Step 1: Pop (0, 0)
        Check (1, 0) -> 'a' from s1 matches 'a' from s3 -> Enqueue (1, 0)
        Check (0, 1) -> 'd' from s2 does not match 'a' from s3 -> Do not enqueue
        Queue Now: [(1, 0)]

Step 2: Pop (1, 0)
        Check (2, 0) -> 'a' from s1 matches 'a' from s3 -> Enqueue (2, 0)
        Check (1, 1) -> 'd' from s2 does not match 'a' from s3 -> Do not enqueue
        Queue Now: [(2, 0)]

Step 3: Pop (2, 0)
        Check (3, 0) -> 'b' from s1 matches 'b' from s3 -> Enqueue (3, 0)
        Check (2, 1) -> 'd' from s2 does not match 'b' from s3 -> Do not enqueue
        Queue Now: [(3, 0)]

Step 4: Pop (3, 0)
        Check (4, 0) -> 'c' from s1 matches 'c' from s3 -> Enqueue (4, 0)
        Check (3, 1) -> 'd' from s2 does not match 'c' from s3 -> Do not enqueue
        Queue Now: [(4, 0)]

Step 5: Pop (4, 0)
        Check (5, 0) -> Index out of range for s1 -> Do not enqueue
        Check (4, 1) -> 'a' from s2 matches 'a' from s3 -> Enqueue (4, 1)
        Queue Now: [(4, 1)]

Continue until the queue is empty or (len(s1), len(s2)) is reached, indicating success.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

这种 ASCII 图解方式直观地展示了 BFS 方法如何逐步探索不同的状态路径，来验证 s3 是否能由 s1 和 s2 交错形成。通过这样的可视化，可以更容易地理解和教授交错字符串问题的 BFS 解决方案，尤其是在探讨算法课程或演示中。

不同算法的优劣势对比

应用示例

这些方法适用于任何需要解析和验证交错字符串的场景，例如编译器的字符串解析、自然语言处理中的句子解构，或者在软件开发中验证输入格式的正确性。