LeetCode Problem 97-Interleaving String

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

示例 1:

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

示例 2:

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

思路一

穷举法,使用递归的思路,遍历s1s2 组成的所有可能的交错字符串,判断是否与 s3 相同,交错字符串的组成方式如下所示:

1
2
3
4
5
6
7
     0
    / \
   /   \
  a     d     左支从 s1 选择,右支从 s2 选择
 / \   / \
aa ad da db   左支从 s1 选择,右支从 s2 选择
    ...

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        def is_interleave(i, j, res):
            if res == s3 and i == len(s1) and j == len(s2):
                return True
            ans = False
            if i < len(s1):
                ans |= is_interleave(i+1, j, res+s1[i])
            if j < len(s2):
                ans |= is_interleave(i, j+1, res+s2[j])
            return ans
        
        return is_interleave(0, 0, '')

时间复杂度 分别是 s1s2 的长度。

思路二

穷举法,但是进行剪枝处理。步骤如下:

  1. 从下标 0, 0, 0 开始,比较 s1[i] == s3[k] 或者 s2[j] == s3[k]
  2. valid = True 当且仅当 ijk 匹配并且剩下的串也是 valid
  3. 只需要保存 invalid[i][j],因为大多数 s1[0:i]s2[0:j] 都不能组成 s3[0:k],保存 valid[i][j] 效果也是一样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        def is_interleave(i, j, k, invalid):
            if i == len(s1):
                return s2[j:] == s3[k:]
            if j == len(s2):
                return s1[i:] == s3[k:]
            if invalid[i][j]:
                return False
            valid = s3[k] == s1[i] and is_interleave(i+1, j, k+1, invalid) or \
                    s3[k] == s2[j] and is_interleave(i, j+1, k+1, invalid)
            if not valid:
                invalid[i][j] = True
            return valid
        
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        invalid = [[False] * n for _ in range(m)]
        return is_interleave(0, 0, 0, invalid)

时间复杂度 ,但是要小于思路一的时间复杂度。

思路三

动态规划。dp[i][j] 表示 s1[:i]s2[:j] 组成的交错字符串是否与 s3[0:i+j] 相匹配。类似编辑距离。详见链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [[True] * (n+1) for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i == 0 and j == 0:
                    dp[i][j] == True
                elif i == 0:
                    dp[i][j] = dp[i][j-1] and s2[j-1] == s3[i+j-1]
                elif j == 0:
                    dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1]
                else:
                    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[m][n]

时间复杂度

思路四

动态规划,可以使用一维数组保存思路三中的 dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [True] * (n+1)
        for i in range(m+1):
            for j in range(n+1):
                if i == 0 and j == 0:
                    dp[j] == True
                elif i == 0:
                    dp[j] = dp[j-1] and s2[j-1] == s3[i+j-1]
                elif j == 0:
                    dp[j] = dp[j] and s1[i-1] == s3[i+j-1]
                else:
                    dp[j] = dp[j] and s1[i-1] == s3[i+j-1] or \
                            dp[j-1] and s2[j-1] == s3[i+j-1]
        return dp[n]

时间复杂度

此时不赞何时赞!