LeetCode97交叉字符串
题目描述
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
解题思路
关于字符串匹配的问题,建议一般不考虑使用递归来做,使用递归很容易造成超时。
对于字符串匹配及子序列问题,一般可考虑使用二维数组做动态规划。使用数组来标记动态规划过程中的状态,核心就是找到在这个动态规划过程中的递推公式。
对于本题,首先如果 s1
s2
s3
都为空的话,是返回 True
的,如果 s1
s2
的长度之和不等于 s3
的长度的话,是返回 False
的。
字符串匹配的过程,类似于是在一个二维矩阵中不断穿梭,讨论可达性的问题。
首先,初始化:
对于第0行,如果s1
为空的话,如果想返回True,则 S2 = S3,将S2与S3逐个匹配,如果 S2[index]==S3[index]
且前一个状态为 True,则将相应的矩阵值设为 True。
对于第0列,与上同理。先将整个矩阵的第0行与第0列进行初始化。
计算中间过程:
对于矩阵中其他位置的值,分析可得,一个位置如果想为True,则需要其左侧(j-1)或者上方(i-1)必有True值。
如果 matrix[i][j-1]
处的值为True的话,即左侧为True,需要判断S2中的当前位置与S3中的位置是否相等,即 S2[j-1]==S3[j-1+i]
,如果相等,则可设为True,如果不想等,可继续判断上方是否可达。
如果martix[i-1][j]
处的值为True的话,即上方为True,需要判断 S1[i-1]==S3[i-1+j]
,如果相等,则该位置可设为True。
最后只需判断matrix[len(s1)][len(s2)]
处是否为True即可。
代码实现
使用Python实现的代码,github地址
核心代码:
class Solution:
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if s1 == s2 == s3 == "":
return True
if len(s1) + len(s2) != len(s3):
return False
# 初始化矩阵
matrix = []
for i in range(len(s1) + 1):
matrix.append([False] * (len(s2) + 1))
matrix[0][0] = True
# 初始化边缘
for i in range(1, len(s1) + 1):
matrix[i][0] = (matrix[i - 1][0] and (s1[i - 1] == s3[i - 1]))
for j in range(1, len(s2) + 1):
matrix[0][j] = (matrix[0][j - 1] and (s2[j - 1] == s3[j - 1]))
# 循环计算每个节点是否可达
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
top = matrix[i - 1][j] and s1[i - 1] == s3[i - 1 + j]
left = matrix[i][j - 1] and s2[j - 1] == s3[j - 1 + i]
matrix[i][j] = top or left
return matrix[len(s1)][len(s2)]