本文主要是介绍力扣-97 交错字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、一开始的想法是利用双指针，给s1和s2各分配一个头指针，每次遇到符合要求的，就将其向右移动，直到最后完成。
但是最后发现问题在于：不方便判断s3的当前字符来自s1还是s2！
'''
https://leetcode-cn.com/problems/interleaving-string/
'''
class Solution1:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:# 利用双指针，每次遇到符合要求的，就将其向右移动，直到最后# 有问题/错误：如何判断当前字符来自s1还是s2s1_left, s2_left = 0, 0s1_n = len(s1)s2_n = len(s2)n = len(s3)for i in range(n):# print(i, s1_left)if s1_left < s1_n and s3[i] == s1[s1_left]:s1_left += 1elif s2_left < s2_n and s3[i] == s2[s2_left]:s2_left += 1else:return Falsereturn True动态规划：
当s1的第i个数和s3的第i+j个数相同时，那么s1的前i个数和s2的前j个数是否交错组成s3的前i+j个数，取决于s1的前i-1个数和s2的前j个数是否交错组成s3的前i+j-1个数；
同理，当s2的第j个数和s3的第i+j个数相同时，那么s1的前i个数和s2的前j个数是否交错组成s3的前i+j个数，取决于s1的前i个数和s2的前j-1个数是否交错组成s3的前i+j-1个数。
class Solution2:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:# 定义dp数组--dp[i][j]表示：s3[0:i+j]是否有s1[0:i]和s2[0:j]交错组成n, m, t = len(s1), len(s2), len(s3)if n + m != t:return Falsedp = [[False]*(m+1) for _ in range(n+1)]# 初始化s3[0:0] = s1[0:0] + s2[0:0]dp[0][0] = True# 初始化s3的第0行和第0列for i in range(1, n+1):if s3[:i] == s1[:i]:dp[i][0] = Trueelse:breakfor j in range(1, m+1):if s3[:j] == s2[:j]:dp[0][j] = Trueelse:breakfor i in range(1, n+1):for j in range(1, m+1):# s1[i-1] or s2[j-1] = s3[i+j-1]# 状态转移方程# 当s1的第i个数和s3的第i+j个数相同时；# 那么s1的前i个数和s2的前j个数是否交错组成s3的前i+j个数---取决于s1的前i-1个数和s2的前j个数是否交错组成s3的前i+j-1个数if s3[i+j-1] == s1[i-1]:dp[i][j] |= dp[i-1][j]if s3[i+j-1] == s2[j-1]:dp[i][j] |= dp[i][j-1]return dp[n][m]
这篇关于力扣-97 交错字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
