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.
1class
The Java dynamic programming solution involves a three-dimensional boolean array dp, which records whether snippets of s1 can scramble into snippets of s2. By building up from single characters to full strings, it ensures that all possible scrambles are evaluated efficiently.