Interleaving String

这道题问s3是不是s1和s2两个数组交叉组合在一起的，这里的交叉组合的意思是说s3中的一段字符可以是s1或者s2中的一段字符串按顺序直接移植或s1和s2按顺序混合插入进来的，也就是说如果插入了i-j的字符，就必须连续插入这段且不能再去找i之前的那一段了，所以根据这个要求就可以发现s3在第k个字符时的选择必然是s1[i + 1]或者s2[j + 1]（i + j = k - 1)，如果这两个字符和s3[k + 1]都不相等，则这个s3就不是这两个字符串交叉组合成的，状态的初始化可以看做单纯用一个s1或者一个s2去检查s3是否是interleaving string，下面是状态方程可以帮助更好理解

dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])

由上面状态方程可以看出此题就是一个匹配类动态规划了，可以从矩阵的零点逐渐递推到最后结果，下面是代码

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        n = len(s1)
        if not n:
            return s2 == s3

        m = len(s2)
        if not m:
            return s1 == s3

        if n + m != len(s3):
            return False

        dp = [([False] * (m + 1)) for _ in xrange(n + 1)]
        dp[0][0] = True

        for i in xrange(1, m + 1):
            dp[0][i] = (dp[0][i - 1] and s2[i - 1] == s3[i - 1])

        for i in xrange(1, n + 1):
            dp[i][0] = (dp[i - 1][0] and s1[i - 1] == s3[i - 1])

        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                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[n][m]

下面是空间优化版，此题可以把空间优化为一排也就是O(m)或者O(n)

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

        dp = [False] * (m + 1)

        for i in xrange(n + 1):
            for j in xrange(m + 1):
                if i == 0 and j == 0:
                    dp[i] = True
                elif not i:
                    dp[j] = (dp[j - 1] and (s2[j - 1] == s3[j - 1]))
                elif not j:
                    dp[j] = (dp[j] and (s1[i - 1] == s3[i - 1]))
                else:
                    left = (dp[j] and (s1[i - 1] == s3[i + j - 1]))
                    right = (dp[j - 1] and (s2[j - 1] == s3[i + j - 1]))
                    dp[j] = (left or right)

        return dp[m]