LeetCode97交叉字符串

发表于 | 更新于 | 分类于 |
字符串匹配问题，一般都需要考虑使用一个动态dp数组

题目描述

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

示例 1:

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

示例 2:

1
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地址

核心代码：

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
30
31
32
33
34
35
36
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)]