{x}
blog image

Scramble String

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.

 

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

 

Constraints:

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

Solution Explanation for Scramble String

This problem asks whether string s2 can be obtained by scrambling string s1 using a recursive algorithm that splits the string, swaps substrings, and recurses on the substrings. We'll explore two approaches: Memorized Search (top-down) and Dynamic Programming (bottom-up).

Both approaches leverage the observation that if s2 is a scrambled version of s1, then their character frequencies must be identical. This provides a quick initial check to prune impossible cases.

Approach 1: Memorized Search (Top-Down)

This approach uses recursion with memoization to avoid redundant computations. The core recursive function dfs(i, j, k) checks if the substring of length k starting at index i in s1 can be scrambled to match the substring of length k starting at index j in s2.

Algorithm:

  1. Base Case: If k (substring length) is 1, compare the characters s1[i] and s2[j]. If they are equal, return true; otherwise, return false.

  2. Recursive Step: Iterate through possible split points h (1 ≤ h < k). For each split:

    • Check if the first h characters of s1 (from i to i+h-1) can scramble to the first h characters of s2 (from j to j+h-1) AND the remaining k-h characters of s1 (from i+h to i+k-1) can scramble to the remaining k-h characters of s2 (from j+h to j+k-1). If this is true, return true.
    • Check if the first h characters of s1 can scramble to the last h characters of s2 (from j+k-h to j+k-1) AND the remaining k-h characters of s1 can scramble to the first k-h characters of s2 (from j to j+k-h-1). If this is true, return true.

  3. Memoization: Store the results of dfs(i, j, k) in a memoization table (cache in Python, f in Java/C++/Go/TypeScript/C#) to avoid recomputation.

  4. Return Value: If none of the above conditions are met, return false.

Time Complexity: O(n4) due to three nested loops (i, j, k) and one loop inside for h. Space Complexity: O(n3) to store the memoization table.

Approach 2: Dynamic Programming (Bottom-Up)

This approach iteratively builds a solution from smaller subproblems to larger ones. We use a 3D array f[i][j][k] where f[i][j][k] is true if the substring of length k starting at i in s1 can scramble to the substring of length k starting at j in s2, and false otherwise.

Algorithm:

  1. Base Case: Initialize f[i][j][1] to true if s1[i] == s2[j], false otherwise.

  2. Iteration: Iterate through substring lengths k from 2 to n. For each length, iterate through starting indices i and j in s1 and s2 respectively.

  3. State Transition: For each k, i, and j, iterate through possible split points h (1 ≤ h < k). If either of the two conditions from the recursive approach are true (f[i][j][h] && f[i+h][j+h][k-h] or f[i][j+k-h][h] && f[i+h][j][k-h]), then set f[i][j][k] to true.

  4. Return Value: Return f[0][0][n].

Time Complexity: O(n4) due to the four nested loops. Space Complexity: O(n3) for the 3D DP table.

The provided code snippets demonstrate both approaches in multiple programming languages. Both approaches have the same time and space complexity, but the dynamic programming solution might be slightly faster in practice due to the lack of recursive function call overhead. However, the memorized search approach might be easier to understand conceptually. Choose the approach based on your preference and understanding.