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

题目描述

97. 交错字符串

给定三个字符串 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], 即只会使用上一行或上一列的状态, 按行或按列滚动即可.

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]这个位置, 则这个位置之后相同的搜索, 肯定会重复多次. 因此有必要加入记忆化, 判断此位置是否已经到达过, 如果到达过, 就可以剪枝了.

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

代码如下:

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思路很接近, 只是一个用递归, 一个用栈, 利用栈的特性.

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）
• 「手画图解」DFS回溯 及其优化
• 动态规划、DFS、BFS全齐活