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.
1using System;
2
public class Solution {
public bool IsScramble(string s1, string s2) {
int n = s1.Length;
if (s1 == s2) return true;
char[] sorted1 = s1.ToCharArray();
Array.Sort(sorted1);
char[] sorted2 = s2.ToCharArray();
Array.Sort(sorted2);
if (!new String(sorted1).Equals(new String(sorted2))) return false;
bool[,,] dp = new bool[n, n, n + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i, j, 1] = s1[i] == s2[j];
}
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
for (int j = 0; j <= n - len; j++) {
for (int k = 1; k < len; k++) {
if ((dp[i, j, k] && dp[i + k, j + k, len - k]) ||
(dp[i, j + len - k, k] && dp[i + k, j, len - k])) {
dp[i, j, len] = true;
break;
}
}
}
}
}
return dp[0, 0, n];
}
}The C# approach is similar to the Java counterpart, using a three-dimensional array to capture scramble possibilities. Early validation of character sequence compatibility is performed to cut down processing time and enhance efficiency.