python实现leetcode之97. 交错字符串

解题思路

启发式的思考，考虑全面就行了，没有什么好说的
添加缓存为了避免重复计算

97. 交错字符串

代码

CACHE = {}
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3): return False
        if not s1: return s2 == s3
        if not s2: return s1 == s3

        key = (s1, s2, s3)
        if key not in CACHE:
            if s1[0] != s3[0] and s2[0] != s3[0]: CACHE[key] = False
            elif s1[0] != s3[0]: CACHE[key] = self.isInterleave(s1, s2[1:], s3[1:])
            elif s2[0] != s3[0]: CACHE[key] = self.isInterleave(s1[1:], s2, s3[1:])
            else:
                CACHE[key] = self.isInterleave(s1, s2[1:], s3[1:]) or self.isInterleave(s1[1:], s2, s3[1:])
        return CACHE[key]