给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
样例 比如 s1 = “aabcc” s2 = “dbbca”
- 当 s3 = "aadbbcbcac"，返回 true. - 当 s3 = "aadbbbaccc"， 返回 false.动态规划 dp[i，j]表示s1的前i个字符与s2的前j个字符能否交叉构成s3的前（i+j）个字符。 对于s3中的第i+j个字符，有以下几种可能：
s3[i+j]==s1[i] and s3[i+j]==s2[j]s3[i+j]==s1[i] and s3[i+j]!=s2[j]s3[i+j]!=s1[i] and s3[i+j]==s2[j]s3[i+j]!=s1[i] and s3[i+j]!=s2[j]第1种，若s1的前i-1个字符与s2的前j个字符能交叉构成s3的前i-1+j个字符，即dp[i-1,j]==True,那么dp[i,j]=True。或者，s2的前j-1个字符和s1的前i个字符能交叉构成s3的前i+j-1个字符，即dp[i,j-1]==True,那么dp[i,j]=True。综上，dp[i,j]=dp[i-1,j] or dp[i,j-1]。
第2种，若s1的前i-1个字符与s2的前j个字符能交叉构成s3的前i-1+j个字符，即dp[i-1,j]==True,那么dp[i,j]=True。 但是，由于s3[i+j]!=s2[j]，所以无论s2的前j-1个字符和s1的前i个字符能否交叉构成s3的前i+j-1个字符，即无论dp[i,j-1]是否为True，dp[i,j]都是False。综上，dp[i,j]=dp[i-1,j]。
第3种与第2种类似。
第4种，dp[i,j]一定为False。
代码如下：
class Solution: """ @param: : A string @param: : A string @param: : A string @return: Determine whether s3 is formed by interleaving of s1 and s2 """ def isInterleave(self, s1, s2, s3): # write your code here、 m=len(s1) n=len(s2) z=len(s3) if m+n!=z: #当长度不匹配时，返回False return False dp=[[0 for x in range(n+1)] for y in range(m+1)] dp[0][0]=True #s1前0个与s2前0个能交叉构成s3前0个 for i in range(1,m+1): #s1前i个与s2前0个能否构成s3前i个 if s1[i-1]==s3[i-1]: dp[i][0]=dp[i-1][0] else: dp[i][0]=False for j in range(1,n+1): #s1前0个与s2前j个能否构成s3前j个 if s2[j-1]==s3[j-1]: dp[0][j]=dp[0][j-1] else: dp[0][j]=False for i in range(1,m+1): #s1前i个与s2前j个能否构成s3前i+j个（i>=1,j>=1） for j in range(1,n+1): if s1[i-1]==s3[i+j-1] and s2[j-1]==s3[i+j-1]: dp[i][j]=(dp[i-1][j] or dp[i][j-1]) elif s1[i-1]==s3[i+j-1]: dp[i][j]=dp[i-1][j] elif s2[j-1]==s3[i+j-1]: dp[i][j]=dp[i][j-1] else: dp[i][j]=False return dp[m][n]