[97][困难][动态规划][DFS][BFS] 交错字符串
题目描述
给定三个字符串 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.
整体代码如下. 时间复杂度和空间复杂度都为. 空间复杂度可以利用滚动数组优化到, 这是因为我们求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参考资料
最后更新于
这有帮助吗？