LeetCode解題之Interleaving String

原題

輸入三個字符串s1、s2和s3，判斷第三個字符串s3是否由前兩個字符串s1和s2交替而成且不改變s1和s2中各個字符原有的相對順序。

注意點：

例子：

輸入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”

輸出: True

解題思路

典型的二維動態規劃題目，dp[i][j]表示s1[:i+1]和s2[:j+1]能否交替組成s3[:i+j+1]，兩個空字符串可以組成空字符串，所以dp[0][0]為True。邊界的情況是一個字符串為空，另一個字符串的頭部是否與目標字符串的頭像相同。而在一般情況下，只有當以下兩種情況之一成立時dp[i][j]為True：

遞推關系式是：dp[i + 1][j + 1] = (dp[j + 1][i] and s1[i] == s3[i + j + 1]) or (dp[j][i + 1] and s2[j] == s3[i + j + 1])

考慮到不同緯度間的數據不干擾，所有可以把二維dp降為一維。

AC源碼

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


if __name__ == "__main__":
    assert Solution().isInterleave("aabcc", "dbbca", "aadbbcbcac") == True
    assert Solution().isInterleave("aabcc", "dbbca", "aadbbbaccc") == False