Sponsored
Sponsored
This approach uses recursion to explore all possible valid splits and checks if either of the permutations exist. To avoid re-computation, use a dictionary to memoize already computed results for specific substrings.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.
1class Solution:
2 def __init__(self):
3 self.memo = {}
4
5 def isScramble(self, s1: str, s2: str) -> bool:
6 if s1 == s2:
7 return True
8 if (s1, s2) in self.memo:
9 return self.memo[(s1, s2)]
10 if sorted(s1) != sorted(s2):
11 return False
12 n = len(s1)
13 for i in range(1, n):
14 if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or \
15 (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
16 self.memo[(s1, s2)] = True
17 return True
18 self.memo[(s1, s2)] = False
19 return FalseThis Python solution uses recursion with memoization, checking all possible partition indices and both possible scrambling options. It uses a dictionary for memoization, speeding up repeated queries. Sorting ensures a quick early rejection of incongruent strings.
This approach is based on dynamic programming. We set up a 3D table where table[i][j][k] holds true if s1's substring starting at index i with length k is a scrambled string of s2's substring starting at index j.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.
1var
The JavaScript solution involves a three-dimensional array to manage the possible scrambling transitions between the strings. The approach includes an initial check for equal character contents using sorting, and it systematically builds potential scrambles from each substring length.