Leetcode 97.交错字符串(Interleaving String)
程序员文章站
2024-02-21 22:12:22
...
Leetcode 97.交错字符串
1 题目描述(Leetcode题目链接)
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
2 题解
动态规划,定义为的前个字符与的前个字符能否交错组成的前个字符。分析比较容易。
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 = [([False]*(n+1)) for _ in range(m+1)]
dp[0][0] = True
for i in range(1, n+1):
dp[0][i] = (s2[i-1] == s3[i-1]) and dp[0][i-1]
for i in range(1, m+1):
dp[i][0] = (s1[i-1] == s3[i-1]) and dp[i-1][0]
for i in range(1, m+1):
for j in range(1, n+1):
dp[i][j] = ((s3[i+j-1] == s1[i-1]) and dp[i-1][j]) or ((s3[i+j-1] == s2[j-1]) and dp[i][j-1])
return dp[-1][-1]
推荐阅读
-
97. Interleaving String 交错字符串
-
97. Interleaving String(交错字符串)
-
Leetcode 97.交错字符串(Interleaving String)
-
C++实现LeetCode(97.交织相错的字符串)
-
LeetCode97交错字符串(JAVA)
-
LeetCode - 1221 - 分割平衡字符串(split-a-string-in-balanced-strings)
-
C++实现LeetCode(97.交织相错的字符串)
-
【leetcode刷题】[简单]443. 压缩字符串(string compression)-java
-
LeetCode——443. 压缩字符串(String Compression)[中等]——分析及代码(Java)
-
Leetcode 443. String Compression--压缩字符串