스크램블 스트링

다음 알고리즘을 사용하여 문자열 s를 스크램블하여 문자열 t를 얻을 수 있습니다.

문자열의 길이가 1이면 중지합니다.

문자열의 길이가 > 1인 경우 다음을 수행합니다.

임의 인덱스에서 문자열을 두 개의 비어 있지 않은 하위 문자열로 분할합니다. 즉, 문자열이 s 인 경우 x 및 y로 나눕니다. 여기서 s = x + y 입니다.

두 개의 하위 문자열을 바꾸거나 동일한 순서로 유지하도록 임의로 결정합니다. 즉, 이 단계 후에 s는 s = x + y 또는 s = y + x가 될 수 있습니다.

두 하위 문자열 x 및 y 각각에 대해 1단계를 재귀적으로 적용합니다.

동일한 길이의 두 문자열 s1 및 s2가 주어지면 true가 s2의 뒤섞인 문자열이면 s1를 반환하고, 그렇지 않으면 false를 반환합니다.

예 1:

입력: s1 = "훌륭함", s2 = "rgeat"
출력: 참
설명: s1에 적용된 한 가지 가능한 시나리오는 다음과 같습니다.
"great"--> "great/eat"//임의 인덱스로 나눕니다.
"gr/eat"--> "gr/eat"//무작위 결정은 두 하위 문자열을 교환하지 않고 순서대로 유지하는 것입니다.
"gr/eat"--> "g/r/e/at"//두 하위 문자열에 동일한 알고리즘을 재귀적으로 적용합니다. 그들 각각을 임의의 인덱스로 나눕니다.
"g/r/e/at"--> "r/g/e/at"//무작위 결정은 첫 번째 하위 문자열을 교체하고 두 번째 하위 문자열을 동일한 순서로 유지하는 것이었습니다.
"r/g/e/at"--> "r/g/e/a/t"//다시 알고리즘을 재귀적으로 적용하고 "at"를 "a/t"로 나눕니다.
"r/g/e/a/t"--> "r/g/e/a/t"//무작위 결정은 두 하위 문자열을 같은 순서로 유지하는 것입니다.
이제 알고리즘이 중지되고 결과 문자열은 s2인 "rgeat"입니다.
한 가지 가능한 시나리오로 인해 s1이 s2로 스크램블되었으므로 true를 반환합니다.

예 2:

입력: s1 = "abcde", s2 = "caebd"
출력: 거짓

예 3:

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

제약:

s1.length == s2.length

1 <= s1.length <= 30

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

해결책:

class Solution:
    def isPos(self, s1, s2, a, b, c, d):
        n = b - a
        if n == 1:
            if s1[a] == s2[c]:
                return True
            else:
                return False
        key = (a, b, c, d)
        if key in self.cache:
            return self.cache[key]
        for l in range(1, n):
            r = n - l
            if self.isPos(s1, s2, a, a + l, c, c + l) and self.isPos(s1, s2, a + l, b, d - r, d):
                self.cache[key] = True
                return True
            if self.isPos(s1, s2, a, a + l, d - l, d) and self.isPos(s1, s2, a + l, b, c, c + r):
                self.cache[key] = True
                return True
        self.cache[key] = False
        return False

    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        self.cache = {}
        return self.isPos(s1, s2, 0, n, 0, n)