87. Scramble String – Leetcode Solutions

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Example 3:

Input: s1 = "a", s2 = "a"
Output: true

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        # A memoization dictionary to store results of subproblems
        memo = {}

        # Helper function that performs the recursive check
        def recursive_check(s1, s2):
            # If both strings are equal, they are trivially scramble strings
            if s1 == s2:
                return True

            # If the lengths are different, they cannot be scramble strings
            if len(s1) != len(s2):
                return False

            # If the sorted characters of both strings are not equal, 
            # they cannot be scramble strings
            if sorted(s1) != sorted(s2):
                return False

            # If the pair (s1, s2) is already computed, return its result
            if (s1, s2) in memo:
                return memo[(s1, s2)]

            n = len(s1)
            for i in range(1, n):
                # Check if there's a valid split that makes s1 and s2 scramble strings
                if (recursive_check(s1[:i], s2[:i]) and recursive_check(s1[i:], s2[i:])) or \
                   (recursive_check(s1[:i], s2[-i:]) and recursive_check(s1[i:], s2[:-i])):
                    memo[(s1, s2)] = True
                    return True

            memo[(s1, s2)] = False
            return False

        # Initial call to the helper function with the full strings
        return recursive_check(s1, s2)

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var isScramble = function(s1, s2) {
    // A memoization object to store results of subproblems
    const memo = {};

    /**
     * Helper function that performs the recursive check
     * @param {string} s1 - first string
     * @param {string} s2 - second string
     * @return {boolean} - whether s2 is a scrambled string of s1
     */
    function recursiveCheck(s1, s2) {
        // If both strings are equal, they are trivially scramble strings
        if (s1 === s2) {
            return true;
        }

        // If the lengths are different, they cannot be scramble strings
        if (s1.length !== s2.length) {
            return false;
        }

        // If the sorted characters of both strings are not equal, 
        // they cannot be scramble strings
        if (s1.split('').sort().join('') !== s2.split('').sort().join('')) {
            return false;
        }

        // If the pair (s1, s2) is already computed, return its result
        if (memo.hasOwnProperty(s1 + '#' + s2)) {
            return memo[s1 + '#' + s2];
        }

        const n = s1.length;
        for (let i = 1; i < n; i++) {
            // Check if there's a valid split that makes s1 and s2 scramble strings
            if ((recursiveCheck(s1.substring(0, i), s2.substring(0, i)) &&
                 recursiveCheck(s1.substring(i), s2.substring(i))) ||
                (recursiveCheck(s1.substring(0, i), s2.substring(n - i)) &&
                 recursiveCheck(s1.substring(i), s2.substring(0, n - i)))) {
                memo[s1 + '#' + s2] = true;
                return true;
            }
        }

        memo[s1 + '#' + s2] = false;
        return false;
    }

    // Initial call to the helper function with the full strings
    return recursiveCheck(s1, s2);
};

import java.util.HashMap;
import java.util.Map;

class Solution {
    // Memoization map to store results of subproblems
    private Map<String, Boolean> memo = new HashMap<>();

    /**
     * Main method to check if s2 is a scrambled string of s1
     * @param s1 - first string
     * @param s2 - second string
     * @return boolean - whether s2 is a scrambled string of s1
     */
    public boolean isScramble(String s1, String s2) {
        // Base case: if both strings are equal
        if (s1.equals(s2)) {
            return true;
        }

        // Base case: if the lengths are different, they cannot be scramble strings
        if (s1.length() != s2.length()) {
            return false;
        }

        // Base case: if sorted characters of both strings are not equal, they cannot be scramble strings
        if (!isAnagram(s1, s2)) {
            return false;
        }

        // Check if the result is already computed and stored in memoization map
        String key = s1 + "#" + s2;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int n = s1.length();
        for (int i = 1; i < n; i++) {
            // Check if there's a valid split that makes s1 and s2 scramble strings
            if ((isScramble(s1.substring(0, i), s2.substring(0, i)) &&
                 isScramble(s1.substring(i), s2.substring(i))) ||
                (isScramble(s1.substring(0, i), s2.substring(n - i)) &&
                 isScramble(s1.substring(i), s2.substring(0, n - i)))) {
                memo.put(key, true);
                return true;
            }
        }

        memo.put(key, false);
        return false;
    }

    /**
     * Helper method to check if two strings are anagrams
     * @param s1 - first string
     * @param s2 - second string
     * @return boolean - whether s1 and s2 are anagrams
     */
    private boolean isAnagram(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] count = new int[26];
        for (char c : s1.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : s2.toCharArray()) {
            if (--count[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    // Memoization dictionary to store results of subproblems
    private Dictionary<string, bool> memo = new Dictionary<string, bool>();

    /**
     * Main method to check if s2 is a scrambled string of s1
     * @param s1 - first string
     * @param s2 - second string
     * @return boolean - whether s2 is a scrambled string of s1
     */
    public bool IsScramble(string s1, string s2) {
        // Base case: if both strings are equal
        if (s1 == s2) {
            return true;
        }

        // Base case: if the lengths are different, they cannot be scramble strings
        if (s1.Length != s2.Length) {
            return false;
        }

        // Base case: if sorted characters of both strings are not equal, they cannot be scramble strings
        if (!IsAnagram(s1, s2)) {
            return false;
        }

        // Check if the result is already computed and stored in memoization dictionary
        string key = s1 + "#" + s2;
        if (memo.ContainsKey(key)) {
            return memo[key];
        }

        int n = s1.Length;
        for (int i = 1; i < n; i++) {
            // Check if there's a valid split that makes s1 and s2 scramble strings
            if ((IsScramble(s1.Substring(0, i), s2.Substring(0, i)) &&
                 IsScramble(s1.Substring(i), s2.Substring(i))) ||
                (IsScramble(s1.Substring(0, i), s2.Substring(n - i)) &&
                 IsScramble(s1.Substring(i), s2.Substring(0, n - i)))) {
                memo[key] = true;
                return true;
            }
        }

        memo[key] = false;
        return false;
    }

    /**
     * Helper method to check if two strings are anagrams
     * @param s1 - first string
     * @param s2 - second string
     * @return boolean - whether s1 and s2 are anagrams
     */
    private bool IsAnagram(string s1, string s2) {
        if (s1.Length != s2.Length) {
            return false;
        }
        int[] count = new int[26];
        foreach (char c in s1) {
            count[c - 'a']++;
        }
        foreach (char c in s2) {
            if (--count[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}