97. Interleaving String

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

        if len(s1) + len(s2) > len(s3):
            return False

        def dfs(i, j, merged):
            if (i, j) in mem:
                return mem[(i, j)]

            if merged and merged[-1] != s3[len(merged) - 1]:
                return False

            if i == len(s1) and j == len(s2):
                return s3 == merged

            res = False
            if i < len(s1):
                res = res or dfs(i + 1, j, merged + s1[i])

            if j < len(s2):
                res = res or dfs(i, j + 1, merged + s2[j])

            mem[(i, j)] = res
            return res

        mem = {}
        return dfs(0, 0, '')