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#
In this C solution, we use a 3D boolean DP array dp with indices [i][j][k] indicating whether a substring starting at index i in s1 and a substring starting at index j in s2 of length k can be scrambles of each other. We fill this array iteratively, considering the divisions of the k-length substring into parts.