本文共 1220 字，大约阅读时间需要 4 分钟。
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example, Given: s1 =“aabcc”, s2 =“dbbca”, When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false.即s3能否被s1和s2交错构成
这道题又是求true or false, 首先想到dp, 只要把dp[[i][j]表示s1[0…i-1]和s2[0…j-1]是否可以拼接为s3[0…i+j-1], 只要把dp[i][j]的表达式想出来，后面也就迎刃而解。但是，前面的初始化部分经常容易遗忘（一般也没dp[i][0]和dp[0][j]这一部分, 当心
class Solution: def isInterleave(self, s1, s2, s3): len1, len2, len3 = len(s1), len(s2), len(s3) if len3 != len1 + len2: return False dp = [[False] * (len2 + 1) for _ in range(len1 + 1)] dp[0][0] = True for i in range(1, len1 + 1): dp[i][0] = s1[:i] == s3[:i] for j in range(1, len2 + 1): dp[0][j] = s2[:j] == s3[:j] for i in range(1, len1 + 1): for j in range(1, len2 + 1): dp[i][j] = (dp[i - 1][j] and s3[i + j - 1] == s1[i - 1]) or ( dp[i][j - 1] and s3[i + j - 1] == s2[j - 1]) return dp[len1][len2]if __name__ == '__main__': s1 = "aabcc" s2 = "dbbca" s3 = "aadbbcbcac" # s3 = "aadbbbaccc" so = Solution() print(so.isInterleave(s1, s2, s3))
转载地址：http://hejmb.baihongyu.com/