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.
1#include <string>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6 unordered_map<string, bool> memo;
7public:
8 bool isScramble(string s1, string s2) {
9 if (s1 == s2) return true;
10 int n = s1.size();
11 string key = s1 + " " + s2;
12 if (memo.count(key)) return memo[key];
13 if (!hasSameChars(s1, s2)) return false;
14 for (int i = 1; i < n; ++i) {
15 if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) ||
16 (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i)))) {
17 return memo[key] = true;
18 }
19 }
20 return memo[key] = false;
21 }
22private:
23 bool hasSameChars(const string &s1, const string &s2) {
24 int charCount[26] = {0};
25 for (char c : s1) charCount[c - 'a']++;
26 for (char c : s2) charCount[c - 'a']--;
27 for (int count : charCount) if (count != 0) return false;
28 return true;
29 }
30};This C++ solution uses recursion with memoization and string manipulation. The memoization map reduces redundant computations by storing results for string combinations. The hasSameChars function checks for character equality in the substrings, pruning unnecessary calculations.
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.