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.
1import java.util.*;
2
3class Solution {
4 private Map<String, Boolean> memo = new HashMap<>();
5
6 public boolean isScramble(String s1, String s2) {
7 if (s1.equals(s2)) return true;
8 int n = s1.length();
9 String key = s1 + " " + s2;
10 if (memo.containsKey(key)) return memo.get(key);
11 if (!hasSameChars(s1, s2)) return false;
12 for (int i = 1; i < n; i++) {
13 if ((isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) ||
14 (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, n - i)))) {
15 memo.put(key, true);
16 return true;
17 }
18 }
19 memo.put(key, false);
20 return false;
21 }
22
23 private boolean hasSameChars(String s1, String s2) {
24 int[] count = new int[26];
25 for (char c : s1.toCharArray()) count[c - 'a']++;
26 for (char c : s2.toCharArray()) count[c - 'a']--;
27 for (int c : count) if (c != 0) return false;
28 return true;
29 }
30}The Java solution uses recursion with memoization to determine if one string is a scrambled version of another. It employs a character count check to quickly eliminate impossible transformations. A HashMap is used to store previously calculated results for specific string combinations. Substring methods are frequently used to examine substring pairs.
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 Python dynamic programming solution uses a 3D list to track potential scrambles from smaller substrings growing up to the full length. It verifies equality between character sets for early exit strategy and leverages the 3D structure to verify combinations of partitions for both swapped and unswapped scenarios.