Scramble String

Problem Statement:-

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.

Link: https://leetcode.com/problems/scramble-string/description/

Problem Explanation with 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
Explanation: It is impossible to obtain s2 from s1 by any means.

Example 3

Input: s1 = "a", s2 = "a"
Output: true
Explanation: Both strings are equal.

Constraints

• s1.length == s2.length

• 1 <= s1.length <= 30

• s1 and s2 consist of lowercase English letters.

Intuition:-

• It is one of the partition DP problems.

• We can partition the string into two parts at every index.

• Then there are two choices - either swap the two parts or not.

• The swap case will check the left part of s1 with the right part of s2 and vice versa.

• Not swap case will check the left part of s1 with the left part of s2 and vice versa.

• If any of the two cases is true, then we return true.

• Else we return false.

• There are also some base cases - if the strings are equal return true, if the length of the strings is not equal return false if the length of the string is 1 and the strings are not equal return false.

• We can memoize the function to reduce the time complexity.

Solution:-

• Create a function solve that takes two strings as parameters.

• Check if the strings are equal withing the function, if they are return true.

• Check if the length of the strings are not equal or if the sorted strings are not equal or if the length of the string is 1, if any of these are true return false.

• Create a for loop which iterates from 1 to the length of the string.

• Create a notSwap variable which stores the result of calling the solve function with the left part of s1 and left part of s2 and the right part of s1 and right part of s2.

• Create a swap variable which stores the result of calling the solve function with the left part of s1 and right part of s2 and the right part of s1 and left part of s2.

• Check if either of the two variables is true, if they are return true.

• Else return false outside the for loop.

• Return the result of calling the solve function with s1 and s2.

• Create a cache decorator to memoize the function.

Code:-

JAVA Solution

class Solution {
    public boolean isScramble(String s1, String s2) {

        Map<String, Boolean> cache = new HashMap<>();
        return solve(s1, s2, cache);
    }

    private boolean solve(String s1, String s2, Map<String, Boolean> cache) {
        if (s1.equals(s2)) return true;
        if (s1.length() != s2.length() || sortString(s1).compareTo(sortString(s2)) != 0 || s1.length() == 1) return false;
        String key = s1 + ":" + s2;

        if (cache.containsKey(key)) {
            return cache.get(key);
        }

        int n = s1.length();

        for (int i = 1; i < n; i++) {
            boolean notSwap = solve(s1.substring(0, i), s2.substring(0, i)) && solve(s1.substring(i), s2.substring(i));
            boolean swap = solve(s1.substring(0, i), s2.substring(n - i)) && solve(s1.substring(i), s2.substring(0, n - i));

            if (notSwap || swap) {
                cache.put(key, true);
                return true;
            }
        }

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

    private String sortString(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return new String(arr);
    }
}

Python Solution

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def solve(s1,s2):
          n = len(s1)
          if s1 == s2: return True
          if n != len(s2) or sorted(s1) != sorted(s2) or n==1: return False

          for i in range(1,n):
            notSwap = solve(s1[:i],s2[:i]) and solve(s1[i:],s2[i:])
            swap = solve(s1[:i],s2[n-i:]) and solve(s1[i:],s2[:n-i])

            if notSwap or swap: return True

          return False

        return solve(s1,s2)

Complexity Analysis:-

TIME:-

The time complexity of this solution is O(n^4) where n is the length of the input strings. This is because there are two nested loops (for i and j), each of which can run up to n, and within those loops there are two recursive calls to the solve function, each of which takes O(n) time to slice the input strings.

SPACE:-

The space complexity is also O(n^4) due to the use of the cache map, which can store up to O(n^4) key-value pairs in the worst case.

References:-

• DP

• Recursion

• @cache decorator python

Connect with me:-

• Twitter

• Github

• LinkedIn