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.
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.