class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        length_1 = len(s1) + 1
        length_2 = len(s2) + 1
        if len(s1) + len(s2) != len(s3):
            return False
        dp = [[False] * length_2 for i in range(length_1)]
        dp[0][0] = True
        for i in range(1, length_1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
        for j in range(1, length_2):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
        for i in range(1, length_1):
            for j in range(1, length_2):
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (
                    dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
        return dp[length_1 - 1][length_2 - 1]
