leetcode97. 交错字符串（算法：动态规划）

**交错字符串**

给定两个字符串 `s1` 和 `s2`,判断它们是否是交错的。两个字符串都是由相同数量的字符组成,并且每个字符串都只包含小写字母。

一个字符串是另一个字符串的交叉串如果它们的第一个字符相同,然后第二个字符相同,依此类推。如果其中一个字符串的长度比另一个短,那么它就是前几个字符的重复。

**示例**

* `s1 = "aabcc"`、`s2 = "dbcca"`,返回 `true`
* `s1 = "aabcc"`、`s2 = "cbca"`，返回 `false`

**动态规划**

我们可以使用动态规划来解决这个问题。我们创建一个二维数组 `dp` 来存储两个字符串的交叉结果。

def isInterleave(s1, s2):
 m, n = len(s1), len(s2)
 # 如果两个字符串长度之和不等于总长度，则返回 False if m + n != len(s1) + len(s2):
 return False dp = [[False] * (n +1) for _ in range(m +1)]
 # 初始化第一行和第一列 for i in range(m +1):
 dp[i][0] = s1[:i] == s2[:i]
 for j in range(n +1):
 dp[0][j] = s1[:j] == s2[:j]
 # 填充二维数组 for i in range(1, m +1):
 for j in range(1, n +1):
 if s1[i -1] == s2[j -1]:
 dp[i][j] = dp[i -1][j -1]
 elif (s1[i -1] == s2[j]) and not dp[i -1][j]:
 dp[i][j] = True elif (s2[j -1] == s1[i]) and not dp[i][j -1]:
 dp[i][j] = True return dp[m][n]

print(isInterleave("aabcc", "dbcca")) # Trueprint(isInterleave("aabcc", "cbca")) # False