101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Recursive Approach with Memoization - Complex approach
  2. Dynamic Programming Approach - Complex approach

Approach 1: Recursive Approach with Memoization

The problem can be solved recursively by checking if two strings are scrambles of each other. For each pair of strings, we can:

  1. Check if they are identical (base case)
  2. Check if they have the same character frequencies
  3. Try all possible ways to split the strings and check if the resulting substrings are scrambles of each other

Since this recursive approach leads to many overlapping subproblems, we can use memoization to avoid redundant calculations.

Algorithm:

  1. Create a memoization map to store results of subproblems.
  2. If the two strings are identical, return true.
  3. If the lengths of the strings are different, return false.
  4. Check if the strings have the same character frequencies. If not, return false.
  5. For each possible split position i (from 1 to length-1):
  6. Check if (s1[0:i] is a scramble of s2[0:i] AND s1[i:] is a scramble of s2[i:]) OR
  7. Check if (s1[0:i] is a scramble of s2[length-i:] AND s1[i:] is a scramble of s2[0:length-i]).
  8. If any of these conditions are true, return true.
  9. Otherwise, return false.

Time Complexity:

O(n^4)

Where n is the length of the strings. There are O(n^2) possible subproblems (considering all possible substrings of s1 and s2), and for each subproblem, we try O(n) different split positions. With memoization, each subproblem is solved only once.

Space Complexity:

O(n^3)

We need O(n^3) space for the memoization map to store results for all possible subproblems. The recursion stack also uses O(n) space in the worst case.

Approach 2: Dynamic Programming Approach

We can also solve this problem using dynamic programming. We'll define a 3D DP array where dp[i][j][k] represents whether the substring of s1 starting at index i with length k is a scramble of the substring of s2 starting at index j with length k.

The base case is when k=1, where we simply check if the characters are the same. For larger values of k, we try all possible ways to split the strings and check if the resulting substrings are scrambles of each other.

Algorithm:

  1. Create a 3D DP array dp[n][n][n+1], where n is the length of the strings.
  2. Initialize the base case: dp[i][j][1] = (s1[i] == s2[j]) for all valid i and j.
  3. For each length k from 2 to n:
  4. For each starting index i in s1 from 0 to n-k:
  5. For each starting index j in s2 from 0 to n-k:
  6. For each split position l from 1 to k-1:
  7. Check if (dp[i][j][l] AND dp[i+l][j+l][k-l]) OR (dp[i][j+k-l][l] AND dp[i+l][j][k-l]).
  8. If any of these conditions are true, set dp[i][j][k] = true.
  9. Return dp[0][0][n].

Time Complexity:

O(n^4)

Where n is the length of the strings. We have O(n^3) states in our DP array, and for each state, we try O(n) different split positions.

Space Complexity:

O(n^3)

We need O(n^3) space for the 3D DP array to store results for all possible subproblems.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function isScramble(s1, s2):
    // Base cases
    if s1 == s2:
        return true
    if length of s1 != length of s2:
        return false
 
    // Check if the strings have the same character frequencies
    if sorted(s1) != sorted(s2):
        return false
 
    // Create a memoization map
    memo = {}
 
    function isScrambleHelper(s1, s2):
        // Check if we've already computed this result
        if (s1, s2) in memo:
            return memo[(s1, s2)]
 
        // Base case
        if s1 == s2:
            memo[(s1, s2)] = true
            return true
 
        // Check character frequencies
        if sorted(s1) != sorted(s2):
            memo[(s1, s2)] = false
            return false
 
        n = length of s1
 
        // Try all possible split positions
        for i from 1 to n-1:
            // Check if we can get s2 by keeping the order of substrings
            if (isScrambleHelper(s1[0:i], s2[0:i]) and isScrambleHelper(s1[i:], s2[i:])):
                memo[(s1, s2)] = true
                return true
 
            # Check if we can get s2 by swapping the substrings
            if (isScrambleHelper(s1[0:i], s2[n-i:]) and isScrambleHelper(s1[i:], s2[0:n-i])):
                memo[(s1, s2)] = true
                return true
 
        memo[(s1, s2)] = false
        return false
 
    return isScrambleHelper(s1, s2)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone