动态规划, dp[i][j] = m的含义是s1的前i个字母和s2的前j个字母可以成功组成s3的前m个字母, 当dp[len_s1][len_s2]==len_s3时返回True。

class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        len1 = len(s1); len2 = len(s2); len3 = len(s3)
        if len1 + len2 != len3:
            return False
        dp = [[0 for i in xrange(len2 + 1)] for j in xrange(len1 + 1)]
        for i in xrange(len1 + 1):
            for j in xrange(len2 + 1):
                if i > 0 and dp[i-1][j] == i - 1 + j and s1[i-1] == s3[i+j-1]:
                    dp[i][j] = i + j
                if j > 0 and dp[i][j-1] == i + j - 1 and s2[j-1] == s3[i+j-1]:
                    dp[i][j] = i + j
        return dp[len1][len2] == len3