给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” 输出: true
示例 2:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” 输出: false
第一次的代码： 递归判断
def jc(s1,s2,s3): if len(s3)!=len(s1)+len(s2): return False if s3=='': return True else: a=s3[0] if s1 and a == s1[0] and jc(s1[1:],s2,s3[1:]):#若s3[0]是s1[0] return True if s2 and a == s2[0] and jc(s1,s2[1:],s3[1:]):#若s3[0]是s2[0] return True return False#若以上两种情况都不成立，返回False return jc(s1,s2,s3)在倒数第二个例子超时了。
第二次代码： 采用动态规划，做完这题还是有一些心得，即s1,s2每次只能拿出第一个字母来组成s3，首先写出dp表的第一行，第一列，dp[0][0]指的是s1,s2都为空的时候，这时候是True，对于第一排，dp[0][1]要为T，首先s1的第一个字母要和s3[0]相同才行，列也是一样的。两个for循环执行dp[i][j]的迭代。
if len(s3)!= len(s1+s2):#若长度不符合 return False dp=[[False for i in range(len(s1)+1)] for j in range(len(s2)+1)] dp[0][0]=True for i in range(1,len(s2)+1):#注意for循环里面有一个+1 dp[i][0]=dp[i-1][0] and (s2[i-1]==s3[i-1]) for i in range(1,len(s1)+1): dp[0][i]=dp[0][i-1] and (s1[i-1]==s3[i-1]) for i in range(1,len(s2)+1): for j in range(1,len(s1)+1): #当使用s2的字母,即在dp表往下走一格 dp[i][j]=dp[i][j] or (dp[i-1][j] and (s2[i-1]==s3[i+j-1])) #当使用s1的字母，即在dp表往右走一格，即True的轨迹只能是下或者左 dp[i][j]=dp[i][j] or (dp[i][j-1] and (s1[j-1]==s3[i+j-1])) print(dp) return dp[len(s2)][len(s1)]60ms，排名23%
