Scrambled String

"""
Intuition for Scrambled String (Step-by-Step Breakdown)

Step 1: Identify the Problem Type
---------------------------------
We are given two strings, A and B. We need to check if B is a 'scrambled' version of A. Scrambling involves splitting a string into two non-empty parts and potentially swapping them. This 'splitting' or breaking the strings into different parts behavior points directly to the Matrix Chain Multiplication (MCM) pattern.

Step 2: Pre-condition Checks (The 'Cheap' Checks)
-------------------------------------------------
Before diving into recursion, we check the basics:
- If lengths are different, they can't be scrambled versions (return False).
- If strings are identical, they are scrambled versions (return True) because 0 swap needed.

Step 3: Finding the 'k' (The Split Point)
-----------------------------------------
Where can we split string A?
- We can split at any index 'i' from 1 to n-1 because any string can't be empty to swap as per the problem.
- Example: s1 = "great", n = 5.
  Possible splits: ("g", "reat"), ("gr", "eat"), ("gre", "at"), ("grea", "t").

Step 4: The Two Scenarios (Swap vs. No Swap)
--------------------------------------------
When we split string A into (left_A, right_A) and B into (left_B, right_B),
two things could have happened to make them scrambled:

Scenario 1: NO SWAP
   The left part of A matches the left part of B, AND
   the right part of A matches the right part of B.
   Condition: solve(A[0:i], B[0:i]) AND solve(A[i:], B[i:])

Scenario 2: SWAP
   The left part of A matches the RIGHT part of B, AND
   the right part of A matches the LEFT part of B.
   Condition: solve(A[0:i], B[n-i:]) AND solve(A[i:], B[0:n-i])

Step 5: The Recursive Decision
------------------------------
For a split at index 'i', if EITHER Scenario 1 OR Scenario 2 is true,
then the strings are scrambled. We loop 'i' from 1 to n-1 and check this.

Step 6: Base Case
-----------------
- If strings are length 1, compare them directly.
- If strings are empty, they are technically scrambled (though constraints
  usually prevent this).

Step 7: Optimization (Memoization)
----------------------------------
The recursive tree grows exponentially. We use a map (key = "A + ' ' + B")
to store results of sub-problems we've already solved.

T.C: You are going on all the substring of S1 ie. N^2 and for each substring of s1,you are taking the substring of S2 also, but lenght of S2 is same as the substring of s1 so for eg. s1 substring length is 3 then s2 substring length will also be 3 and this way you will be having N substring in s2 of size 3 so each state becomes N^2*N and for each state We try to split on all the string so it becomes O(N) so total O(N^3)*O(N).

Space compleixty= N^3 states so O(N^3) and for each state, you store a string of length N so N^3*n=N^4
"""

#User function Template for python3

def fun(s1,s2,dict):
    # print(s1,s2)
    if len(s1)!=len(s2):
        return False
    if s1==s2:
        return True
    if not s1 or not s2:
        return False
    if (s1,s2) in dict.keys():
        return dict[(s1,s2)]

    flag=False
    n=len(s1)
    for k in range(1,n):
        if fun(s1[:k],s2[n-k:],dict) and fun(s1[k:],s2[:n-k],dict):
            flag=True
            break
        if fun(s1[:k], s2[:k],dict) and fun(s1[k:],s2[k:],dict):
            flag=True
            break
    dict[(s1,s2)]=flag
    return dict[(s1,s2)]

class Solution:
    def isScramble(self,s1: str, s2: str):
        dict={}
        return fun(s1,s2,dict)