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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private Dictionary<string, bool> memo = new Dictionary<string, bool>();
6
7 public bool IsScramble(string s1, string s2) {
8 if (s1 == s2) return true;
9 if (s1.Length != s2.Length) return false;
10
11 string key = s1 + " " + s2;
12 if (memo.ContainsKey(key)) return memo[key];
13 if (!HasSameChars(s1, s2)) return false;
14
15 int n = s1.Length;
16 for (int i = 1; i < n; ++i) {
17 if ((IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) ||
18 (IsScramble(s1.Substring(0, i), s2.Substring(n - i)) && IsScramble(s1.Substring(i), s2.Substring(0, n - i)))) {
19 memo[key] = true;
20 return true;
21 }
22 }
23 memo[key] = false;
24 return false;
25 }
26
27 private bool HasSameChars(string s1, string s2) {
28 int[] count = new int[26];
29 foreach (char c in s1) count[c - 'a']++;
30 foreach (char c in s2) count[c - 'a']--;
31 foreach (int c in count) if (c != 0) return false;
32 return true;
33 }
34}The C# solution operates similarly to the C++ solution. It uses a dictionary for memoization to minimize redundant calculations and includes a character frequency verification method. Recursion handles all possible string splits and permutations.
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.