本文主要是介绍leetcode97. 交错字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出: true
示例 2:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
输出: false
二维动态规划：
class Solution:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:if sorted(s1+s2) != sorted(s3):return Falseif not s3:return Truelen_1, len_2, len_3 = len(s1), len(s2), len(s3)dp = [[False]*(len_2+1) for _ in range(len_1+1)] # 表示s1前i个和s2前j个能否构成s3前i+j个for i in range(1, len_1+1):if s1[i-1] == s3[i-1]:dp[i][0] = Trueelse:breakfor j in range(1, len_2+1):if s2[j-1] == s3[j-1]:dp[0][j] = Trueelse:breakfor i in range(1, len_1+1):for j in range(1, len_2+1):# 如果s1 i-1个和s2 j个为真且s1 i个和s3 i+j个相同if s1[i-1] == s3[i+j-1] and dp[i-1][j]:dp[i][j] = Truecontinue# 如果s1 i个和s2 j-1个为真且s2 j个和s3 i+j个相同if s2[j-1] == s3[i+j-1] and dp[i][j-1]:dp[i][j] = Truereturn dp[-1][-1]
这篇关于leetcode97. 交错字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
