97. Interleaving String LeetCode

97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

First

解题的重要思路是动态规划，根据子问题得出最终的解，从左到右递归判断从i, j中的其中一个等于l。

1. 若s1[i]等于s3[l], 则继续判断i+1, j, l+1是否依旧能够满足条件。
2. 若s2[j]等于s3[l], 则继续判断i, j+1, l+1是否依旧能够满足条件。
   若都不成立，则判断匹配失败，返回False

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        s1_len = len(s1)
        s2_len = len(s2)
        i, j = 0, 0

        def dfs(i, j, l, cache):
            if (i, j) in cache:
                return cache[(i, j)]
            if i == s1_len:
                return s2[j:] == s3[l:]
            if j == s2_len:
                return s1[i:] == s3[l:]
            result = False
            if s1[i] == s3[l]:
                result = result | dfs(i+1, j, l+1, cache)
            if s2[j] == s3[l]:
                result = result | dfs(i, j+1, l+1, cache)
            cache[(i, j)] = result
            return result
        return dfs(0, 0, 0, {})

s = Solution()
print(s.isInterleave(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))