97. Interleaving String

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.

Solution: DP

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if None in (s1, s2, s3):
            return False
        if len(s1) + len(s2) != len(s3):
            return False

        rows = len(s1) + 1
        cols = len(s2) + 1

        # dp[i][j]: s1[:i] and s2[:j] can interleave into s3[:(i + j)]
        dp = [[False] * cols for _ in xrange(rows)]
        dp[0][0] = True
        for row in xrange(1, rows):
            dp[row][0] = dp[row - 1][0] and s1[row - 1] == s3[row - 1]
        for col in xrange(1, cols):
            dp[0][col] = dp[0][col - 1] and s2[col - 1] == s3[col - 1]

        for row in xrange(1, rows):
            for col in xrange(1, cols):
                char = s3[row + col - 1]
                dp[row][col] = (dp[row][col - 1] and s2[col - 1] == char
                                or dp[row - 1][col] and s1[row - 1] == char)
        return dp[-1][-1]