Solution For Scramble String

The Scramble String problem on LeetCode is a dynamic programming problem that asks us to determine if two given strings are scrambled versions of each other.

To solve this problem, we’ll need to use dynamic programming to build up a memo table that stores the solutions for smaller subproblems. We’ll start with the base case of comparing two single-character strings. If the characters match, we return true. Otherwise, we return false.

Then, we’ll use a nested loop to iterate over all possible splits of the original strings into two substrings. For each split, we’ll recursively check if the two substrings are scrambled versions of each other. We’ll also check the reverse split to handle the case of the second string being the scrambled version of the first.

If any of the splits result in a match, we can return true. Otherwise, we return false.

Here’s the step-by-step solution in Python:

“`python
def isScramble(s1: str, s2: str) -> bool:
# Base case: single characters
if s1 == s2:
return True

# Base case: different lengths or different character sets
if len(s1) != len(s2) or sorted(s1) != sorted(s2):
    return False

# Memo table to store solutions for subproblems
memo = {}

# Recursive function to check if two substrings are scrambled versions
def checkScramble(left1, right1, left2, right2):
    # Check memo table first
    if (left1, right1, left2, right2) in memo:
        return memo[(left1, right1, left2, right2)]

    # Base case: single characters
    if left1 == right1:
        return s1[left1] == s2[left2]

    # Check if substrings are anagrams (optimization)
    if sorted(s1[left1:right1+1]) != sorted(s2[left2:right2+1]):
        return False

    # Try all possible splits
    for i in range(left1, right1):
        if (checkScramble(left1, i, left2, left2+(i-left1)) 
                and checkScramble(i+1, right1, left2+(i-left1)+1, right2)):
            memo[(left1, right1, left2, right2)] = True
            return True

        # Try reverse split as well
        if (checkScramble(left1, i, right2-(i-left1), right2) 
                and checkScramble(i+1, right1, left2, right2-(i-left1)-1)):
            memo[(left1, right1, left2, right2)] = True
            return True

    # Store result in memo table and return false
    memo[(left1, right1, left2, right2)] = False
    return False

# Start recursive calls from the entire strings
return checkScramble(0, len(s1)-1, 0, len(s2)-1)

“`

This solution has a time complexity of O(n^4) due to the nested loops and memo table lookups, but it only uses O(n^3) space for the memo table. With some additional optimizations, such as checking for anagrams and avoiding recursive calls with identical substrings, we can reduce the time complexity to O(n^3).

Step by Step Implementation For Scramble String

public class Solution {
    public boolean isScramble(String s1, String s2) {
        //check if the two strings are the same
        if(s1.equals(s2)) return true; 
        
        //check if the two strings are of the same length
        if(s1.length() != s2.length()) return false;
        
        //check if the two strings are of the same length and don't have the same characters
        int[] letters = new int[26];
        for(int i=0; i
def isScramble(s1, s2):
        # base case
        if s1 == s2: return True
        if len(s1) != len(s2): return False
        # check if the two strings are anagrams of each other
        if sorted(s1) != sorted(s2): return False
        # divide and conquer
        for i in range(1, len(s1)):
            # check if s1[:i] is a scramble of s2[:i] AND s1[i:] is a scramble of s2[i:]
            if isScramble(s1[:i], s2[:i]) and isScramble(s1[i:], s2[i:]): return True
            # check if s1[:i] is a scramble of s2[len(s2)-i:] AND s1[i:] is a scramble of s2[:len(s2)-i]
            if isScramble(s1[:i], s2[len(s2)-i:]) and isScramble(s1[i:], s2[:len(s2)-i]): return True
        return False
var scramble = function(s1, s2) {
    // create a hashmap to store the count of each character in s1
    let map = {};
    for (let i = 0; i < s1.length; i++) {
        if (!(s1[i] in map)) {
            map[s1[i]] = 1;
        } else {
            map[s1[i]]++;
        }
    }
    // check if each character in s2 exists in the hashmap and its count is greater than 0
    // if not, return false
    // else, decrement the count of that character in the hashmap
    for (let i = 0; i < s2.length; i++) {
        if (!(s2[i] in map) || map[s2[i]] === 0) {
            return false;
        } else {
            map[s2[i]]--;
        }
    }
    return true;
};
bool isScramble(string s1, string s2) {
        if(s1.size()!=s2.size()) return false;
        if(s1==s2) return true;
        string str1=s1, str2=s2;
        sort(str1.begin(), str1.end());
        sort(str2.begin(), str2.end());
        if(str1!=str2) return false;
        for(int i=1; i
public class Solution { 
    public bool IsScramble(string s1, string s2) { 
        if (s1 == s2) return true; 
        if (s1.Length != s2.Length) return false; 
        int[] letters = new int[26]; 
        for (int i=0; i