Input: s1 ="great", s2 ="rgeat"Output: trueExplanation: One possible scenario applied on s1 is:"great"-->"gr/eat"// divide at random index.
"gr/eat"-->"gr/eat"// random decision is not to swap the two substrings and keep them in order.
"gr/eat"-->"g/r / e/at"// apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at"-->"r/g / e/at"// random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at"-->"r/g / e/ a/t"// again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t"-->"r/g / e/ a/t"// random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is"rgeat" which is s2.As one possible scenario led s1 to be scrambled to s2, we returntrue.
Recursively check all possible splits of the strings. For each split, try both the non-swapped and swapped cases. Use memoization to avoid redundant computation. If the characters in the substrings do not match, prune early.
Define a recursive function that checks if s1[i:i+len] can be scrambled to s2[j:j+len]. For each possible split, check both the swapped and non-swapped cases. Use a cache to store results for subproblems.
publicbooleanisScramble(String s1, String s2) {
Map<String, Boolean> memo =new HashMap<>();
return dfs(s1, s2, memo);
}
privatebooleandfs(String a, String b, Map<String, Boolean> memo) {
String key = a +"#"+ b;
if (memo.containsKey(key)) return memo.get(key);
if (a.equals(b)) return memo.put(key, true) ==null?true : true;
if (a.length() != b.length()) return memo.put(key, false) ==null?false : false;
char[] ca = a.toCharArray(), cb = b.toCharArray();
Arrays.sort(ca); Arrays.sort(cb);
if (!Arrays.equals(ca, cb)) return memo.put(key, false) ==null?false : false;
int n = a.length();
for (int i = 1; i < n; i++) {
if ((dfs(a.substring(0, i), b.substring(0, i), memo) && dfs(a.substring(i), b.substring(i), memo)) || (dfs(a.substring(0, i), b.substring(n-i), memo) && dfs(a.substring(i), b.substring(0, n-i), memo)))
return memo.put(key, true) ==null?true : true;
}
return memo.put(key, false) ==null?false : false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
funisScramble(s1: String, s2: String): Boolean {
val memo = mutableMapOf<String, Boolean>()
fundfs(a: String, b: String): Boolean {
val key = "$a#$b" memo[key]?.let { returnit }
if (a == b) returntrue.also { memo[key] = true }
if (a.length != b.length) returnfalse.also { memo[key] = false }
if (a.toCharArray().sorted() != b.toCharArray().sorted()) returnfalse.also { memo[key] = false }
val n = a.length
for (i in1 until n) {
if ((dfs(a.substring(0, i), b.substring(0, i)) && dfs(a.substring(i), b.substring(i))) || (dfs(a.substring(0, i), b.substring(n-i)) && dfs(a.substring(i), b.substring(0, n-i))))
returntrue.also { memo[key] = true }
}
returnfalse.also { memo[key] = false }
}
return dfs(s1, s2)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defisScramble(self, s1: str, s2: str) -> bool:
from functools import lru_cache
@lru_cache(maxsize=None)
defdfs(a, b):
if a == b:
returnTrueif len(a) != len(b):
returnFalseif sorted(a) != sorted(b):
returnFalse n = len(a)
for i in range(1, n):
if (dfs(a[:i], b[:i]) and dfs(a[i:], b[i:])) or \
(dfs(a[:i], b[-i:]) and dfs(a[i:], b[:-i])):
returnTruereturnFalsereturn dfs(s1, s2)
Convert the recursive solution to an iterative bottom-up DP. Use a 3D DP table where dp[i][j][len] is true if s1[i:i+len] can be scrambled to s2[j:j+len]. Build up the solution for all substring lengths.
Initialize a 3D DP table. For substrings of length 1, set dp[i][j][1] to true if s1[i] == s2[j]. For longer substrings, try all possible splits and check both swapped and non-swapped cases. Fill the table iteratively.
publicbooleanisScrambleBU(String s1, String s2) {
int n = s1.length();
if (n != s2.length()) returnfalse;
boolean[][][] dp =newboolean[n][n][n+1];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i][j][1]= s1.charAt(i) == s2.charAt(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];
}
funisScrambleBU(s1: String, s2: String): Boolean {
val n = s1.length
if (n != s2.length) returnfalseval dp = Array(n) { Array(n) { BooleanArray(n+1) } }
for (i in0 until n)
for (j in0 until n)
dp[i][j][1] = s1[i] == s2[j]
for (len in2..n) {
for (i in0..(n-len)) {
for (j in0..(n-len)) {
for (k in1 until len) {
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] = truebreak }
}
}
}
}
return dp[0][0][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution:
defisScrambleBU(self, s1: str, s2: str) -> bool:
n = len(s1)
if n != len(s2): returnFalse dp = [[[False]*(n+1) for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
dp[i][j][1] = s1[i] == s2[j]
for l in range(2, n+1):
for i in range(n-l+1):
for j in range(n-l+1):
for k in range(1, l):
if (dp[i][j][k] and dp[i+k][j+k][l-k]) or \
(dp[i][j+l-k][k] and dp[i+k][j][l-k]):
dp[i][j][l] =Truebreakreturn dp[0][0][n]