HomeLeetcode87. Scramble String - Leetcode Solutions
Leetcode

87. Scramble String – Leetcode Solutions

Declan Clarke

Description:

We can scramble a string s to get a string t using the following algorithm:

  1. If the length of the string is 1, stop.
  2. If the length of the string is > 1, do the following:
    • Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
    • Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
    • Apply step 1 recursively on each of the two substrings x and y.

Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.

Examples:

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

Solution in Python:

Python
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)

Explanation:

  1. Memoization Dictionary:
    • We use a dictionary memo to store the results of subproblems. This helps in avoiding recomputation of the same subproblem multiple times.
  2. Recursive Helper Function:
    • The function recursive_check takes two strings, s1 and s2, and checks if s2 is a scrambled version of s1.
  3. Base Cases:
    • If s1 is equal to s2, then they are trivially scrambled strings.
    • If the lengths of s1 and s2 are different, they cannot be scrambled versions of each other.
    • If the sorted characters of s1 and s2 are not the same, they cannot be scrambled versions.
  4. Memoization Check:
    • Before performing the checks, we see if the result for the pair (s1, s2) is already computed and stored in the memo dictionary.
  5. Recursive Splitting and Checking:
    • We try splitting the string s1 at every possible index i (from 1 to n-1) and check both scenarios:
      • The first i characters of s1 with the first i characters of s2 and the remaining with the remaining.
      • The first i characters of s1 with the last i characters of s2 and the remaining with the remaining.
    • If any of these splits result in s2 being a scrambled version of s1, we return True.
  6. Storing the Result:
    • If no valid splits are found, we store False in the memo dictionary for the pair (s1, s2).
  7. Initial Call:
    • The function isScramble initiates the process by calling recursive_check with the full strings s1 and s2.

This solution efficiently handles the problem constraints and ensures that redundant computations are avoided through memoization.

Solution in Javascript:

JavaScript
/**
 * @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);
};

Solution in Java:

Java
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;
    }
}

Solution in C#:

C#
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;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com