Givens1,s2,s3, find whethers3is formed by the interleaving ofs1ands2.
For example,Given:s1="aabcc",s2="dbbca",
Whens3="aadbbcbcac", return true.Whens3="aadbbbaccc", return false.
class Solution:# @return a booleandef isInterleave(self, s1, s2, s3):if len(s1) + len(s2) != len(s3):return Falsedp = [[False for j in range(len(s2) + 1)] for i in range(len(s1) + 1)]dp[0][0] = Truefor row in range(len(s1) + 1):dp[row][0] = s1[:row] == s3[:row]for col in range(len(s2) + 1):dp[0][col] = s2[:col] == s3[:col]for i in range(1, len(s1) + 1):for j in range(1, len(s2) + 1):dp[i][j] = (dp[i – 1][j] and s1[i – 1] == s3[j + i – 1]) or (dp[i][j – 1] and s2[j – 1] == s3[i + j – 1])return dp[-1][-1]
，上帝从不埋怨人们的愚昧，人们却埋怨上帝的不公
