[LeetCode]97 交错字符串

题目描述

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def isInterleave(self, s1, s2, s3,dp={}):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if not s3:
            return not (s1 or s2)
        if (s1, s2, s3) in dp:
            return dp[(s1, s2, s3)]  
        if (s1 and s3[0] == s1[0] and
            self.isInterleave(s1[1:], s2, s3[1:], dp)):
            dp[(s1, s2, s3)] = True
            return True  
        if (s2 and s3[0] == s2[0] and
            self.isInterleave(s1, s2[1:], s3[1:], dp)):
            dp[(s1, s2, s3)] = True
            return True
        dp[(s1, s2, s3)] = False
        return False