Scrambled String Checker

Given two strings, determine if the second string is a "scrambled" version of the first string. A scrambled string is created by taking a string, splitting it into two non-empty substrings at any point, and then optionally swapping these two substrings. This process can be applied recursively to the substrings. This problem is a classic example of dynamic programming or recursion with memoization, often used to test understanding of divide and conquer strategies.

Problem Description

You are tasked with writing a function isScrambled(s1, s2) that returns true if s2 is a scrambled string of s1, and false otherwise.

A string s can be scrambled by:

1. Choosing a non-empty substring at any index i (1 <= i < length of s).
2. Splitting s into two substrings: x = s[0...i-1] and y = s[i...length-1].
3. Either keeping them in the order x + y or swapping them to y + x.
4. Applying this process recursively to x and y.

This recursive scrambling process generates all possible scrambled versions of the original string.

Key Requirements:

• The function must correctly identify if s2 can be formed by scrambling s1.
• The lengths of s1 and s2 must be equal for s2 to be a scramble of s1.

Expected Behavior:

• If s1 and s2 have different lengths, they cannot be scrambles of each other.
• If s1 and s2 are identical, s2 is a scramble of s1.
• The scrambling process is recursive. For example, if s1 = "great", we could split it into "gr" and "eat". If we swap them, we get "eatgr". Now, if we scramble "eat" into "tea", the result could be "teagr".

Edge Cases to Consider:

• Empty strings: While the problem states non-empty substrings, consider how your logic handles empty input strings (though constraints might disallow them).
• Strings of length 1: A string of length 1 is always a scramble of itself.

Examples

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation:
"great" can be split into "gr" and "eat".
If we swap them: "eatgr".
Now, consider "eat". If we split "eat" into "ea" and "t", and swap them: "te" + "a" -> "tea".
So, "rgeat" can be formed as "r" + "geat". "geat" is a scramble of "great".
Let's trace the scrambling more precisely:
"great" -> split at 2: "gr" | "eat"
Swap: "eat" | "gr" -> "eatgr"
Now, let's consider the original "great" and "rgeat".
They have the same characters.
Let's try splitting "great" at index 1: "g" | "reat".
If we swap: "reat" | "g" -> "reatg". This is not "rgeat".
Let's try splitting "great" at index 2: "gr" | "eat".
If we swap: "eat" | "gr" -> "eatgr". This is not "rgeat".
If we DON'T swap: "gr" | "eat" -> "great".
Now, let's look at "rgeat". It has the same characters as "great".
Can we form "rgeat" from "great"?
Consider splitting "great" at index 1: "g" and "reat".
If we don't swap: "g" + scramble("reat"). If scramble("reat") is "reat", then "great". Not "rgeat".
If we swap: scramble("reat") + "g". If scramble("reat") is "reat", then "reatg". Not "rgeat".

Consider splitting "great" at index 2: "gr" and "eat".
If we don't swap: scramble("gr") + scramble("eat").
If we swap: scramble("eat") + scramble("gr").

Let's try matching prefixes. "rgeat" starts with 'r'. "great" has 'r' at index 2.
So, one possible split for "great" is "gr" | "eat".
If we swap them, we get "eat" | "gr".
Now, if we want "rgeat", it might be that 'r' comes from "gr" and "geat" comes from "eat", or vice versa.
Consider s1 = "great", s2 = "rgeat".
If we don't swap:
  s1[0] == s2[0] ? 'g' == 'r' (false)
If we swap:
  s1[0...i-1] vs s2[n-i...n-1] AND s1[i...n-1] vs s2[0...n-i-1]
  OR
  s1[0...i-1] vs s2[0...i-1] AND s1[i...n-1] vs s2[i...n-1]

Let's try a split of "great" at index 1: "g" | "reat".
Option 1 (no swap): isScrambled("g", "r") AND isScrambled("reat", "geat")
Option 2 (swap): isScrambled("g", "t") AND isScrambled("reat", "rgea")

Let's try split of "great" at index 2: "gr" | "eat".
Option 1 (no swap): isScrambled("gr", "rg") AND isScrambled("eat", "eat")
  isScrambled("gr", "rg"):
    split "gr" at 1: "g" | "r"
    No swap: isScrambled("g", "r") AND isScrambled("r", "g") (false)
    Swap: isScrambled("g", "g") AND isScrambled("r", "r") (true && true = true)
    So, isScrambled("gr", "rg") is true.
  isScrambled("eat", "eat"): (true, strings are identical)
  Therefore, Option 1 (no swap for "great" split at 2) returns true.

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false
Explanation:
"abcde" and "caebd" have the same characters, but no sequence of splits and swaps can transform "abcde" into "caebd". For instance, if we split "abcde" into "ab" and "cde", no matter how we scramble "ab" or "cde", and no matter if we swap them, we cannot form "caebd".

Example 3:

Input: s1 = "a", s2 = "a"
Output: true
Explanation: Strings of length 1 are always considered scrambled versions of themselves.

Constraints

• 1 <= s1.length, s2.length <= 30
• s1.length == s2.length
• s1 and s2 consist of lowercase English letters.

Notes

• This problem can be solved using recursion with memoization (dynamic programming).
• Before diving into the recursive logic, consider the base cases and necessary preconditions.
• The key insight is that if s2 is a scramble of s1, then for any split point i in s1, s2 must be formable by either:
  1. scramble(s1[0...i-1]) matched with s2[0...i-1] AND scramble(s1[i...n-1]) matched with s2[i...n-1]
  2. scramble(s1[0...i-1]) matched with s2[n-i...n-1] AND scramble(s1[i...n-1]) matched with s2[0...n-i-1] (where n is the length of the strings)
• Sorting the characters of s1 and s2 can be a quick check to rule out impossible cases early. If the sorted strings are not equal, they cannot be scrambles of each other.