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.
1var isScramble = function(s1, s2) {
2 const memo = new Map();
3 const hasSameChars = (str1, str2) => {
4 const charCount = new Array(26).fill(0);
5 for (let c of str1) charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
6 for (let c of str2) charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]--;
7 for (let count of charCount) if (count !== 0) return false;
8 return true;
9 };
10
11 const scramble = (s1, s2) => {
12 const key = `${s1} ${s2}`;
13 if (memo.has(key)) return memo.get(key);
14 if (s1 === s2) return true;
15 if (!hasSameChars(s1, s2)) return false;
16
17 const n = s1.length;
18 for (let i = 1; i < n; i++) {
19 if ((scramble(s1.substring(0, i), s2.substring(0, i)) && scramble(s1.substring(i), s2.substring(i))) ||
20 (scramble(s1.substring(0, i), s2.substring(n - i)) && scramble(s1.substring(i), s2.substring(0, n - i)))) {
21 memo.set(key, true);
22 return true;
23 }
24 }
25 memo.set(key, false);
26 return false;
27 };
28
29 return scramble(s1, s2);
30};The JavaScript solution implements memoization with a Map to track previously computed results. It verifies character frequencies between the strings for early exits. The main recursive function evaluates each partition index and both permutations of swapping and not swapping substrings.
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>
using 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.