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#include <string>
2using namespace std;
class Solution {
public:
bool isScramble(string s1, string s2) {
int n = s1.size();
if (s1 == s2) return true;
if (!hasSameChars(s1, s2)) return false;
bool dp[n][n][n+1];
memset(dp, false, sizeof(dp));
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];
}
private:
bool hasSameChars(const string &s1, const string &s2) {
int charCount[26] = {0};
for (char c : s1) charCount[c - 'a']++;
for (char c : s2) charCount[c - 'a']--;
for (int count : charCount) if (count != 0) return false;
return true;
}
};The C++ solution uses a similar 3D DP table as above, filled iteratively. The table checks all substring lengths systematically, marking whether s1's substring can scramble to become s2's substring. A character comparison guards against unnecessary calculations.