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.
1#
In this C solution, we use a 3D boolean DP array dp with indices [i][j][k] indicating whether a substring starting at index i in s1 and a substring starting at index j in s2 of length k can be scrambles of each other. We fill this array iteratively, considering the divisions of the k-length substring into parts.