인터리빙 문자열

주어진 문자열 s1 , s2 및 s3 에서 s3 가 s1 및 s2 의 인터리빙에 의해 형성되는지 확인합니다.

두 문자열s 및 t의 인터리빙은 다음과 같이 비어 있지 않은 하위 문자열로 분할되는 구성입니다.

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| <= 1

인터리빙은 s1 + t1 + s2 + t2 + s3 + t3 + ... 또는 t1 + s1 + t2 + s2 + t3 + s3 + ...입니다.

참고: a + b는 문자열 a 및 b의 연결입니다.

예 1:



입력: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
출력: 참

예 2:

입력: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
출력: 거짓

예 3:

입력: s1 = "", s2 = "", s3 = ""
출력: 참

제약:

0 <= s1.length, s2.length <= 100

0 <= s3.length <= 200

s1 , s2 및 s3 는 영문 소문자로 구성됩니다.

후속 작업: 추가 메모리 공간O(s2.length)만 사용하여 문제를 해결할 수 있습니까?

해결책:

class Solution:
    def isLeave(self, s1, s2, s3, i, j, k, m, n, p):
        if (i, j, k) in self.cache:
            return self.cache[(i,j,k)]
        if i >= m or j >= n or k >= p:
            if i >= m:
                res = s2[j:] == s3[k:]
                self.cache[(i,j,k)] = res
                return res
            if j >= n:
                res = s1[i:] == s3[k:]
                self.cache[(i,j,k)] = res
                return res
            self.cache[(i,j,k)] = False
            return False
        if s1[i] == s3[k] and self.isLeave(s1, s2, s3, i + 1, j, k + 1, m, n, p):
            self.cache[(i,j,k)] = True
            return True
        if s2[j] == s3[k] and self.isLeave(s1, s2, s3, i, j + 1, k + 1, m, n, p):
            self.cache[(i,j,k)] = True
            return True
        self.cache[(i,j,k)] = False
        return False

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m = len(s1)
        n = len(s2)
        p = len(s3)
        self.cache = {}
        return self.isLeave(s1, s2, s3, 0, 0, 0, m, n, p)