In this problem, we must determine whether one string can be transformed into another by performing a series of character splits and swaps. This concept has practical applications in cryptography, where strings are often manipulated through various operations to achieve encryption or decryption. Additionally, it is relevant in data compression algorithms that rearrange or transform strings to optimize space usage. Imagine we’re playing a word game where you have a set of letters, and our goal is to create as many valid words as possible with those letters. This is similar to the Scramble String problem.

In the illustration above, we can see that `great`

can be scrambled to `rgaet`

. Here, we’ll explore the problem statement and provide a Python solution and explanation.

Given two strings, `s1`

and `s2`

of the same length, return TRUE if `s2`

is a scrambled string of `s1`

; otherwise, return FALSE.

To get one string from another, we need to follow the steps below:

If the string’s length is

`1`

, no further action is taken.If the string’s length is greater than

`1`

, perform the following:Divide the string into two substrings (nonempty) at a random index. In other words, if the string is

`s`

, we can split it into two parts:`x`

and`y`

, such that`s = x + y`

.Either swap the positions of the substrings or keep them in their original order (the decision is taken randomly). This means

`s`

may become`s = x + y`

or`s = y + x`

.Apply the scrambling process recursively to the two substrings,

`x`

and`y`

. Given two strings,`s1`

, and`s2`

, which have the same length; the goal is to determine whether`s2`

can be derived from applying the scramble operation on`s1`

. If this is possible, return`True`

; otherwise, return`False`

.

Attempt the quiz below to test your concepts on this problem:

1

What is the *Scramble String* problem in Python?

A)

Rearranging characters in a string to form a palindrome

B)

Splitting a string into two substrings and swapping them to match another string

C)

Finding the longest common subsequence between two strings

D)

A problem that involves reversing a string

Question 1 of 30 attempted

We use a dynamic programming approach with a 3D table to store intermediate results efficiently, avoiding redundant computations and facilitating memoization, thus improving the algorithm’s efficiency.

The algorithm can be described as follows:

**Base case:**If the lengths of

`s1`

and`s2`

are not equal, return FALSE as the transformation is not possible.

**Table initialization:**Create a 3D table

`table`

with dimensions`[n][n][n + 1]`

where`n`

is the length of the strings`s1`

and`s2`

. Initialize all values to FALSE.

**Base case for single characters:**Iterate over characters in both strings. If characters in the same positions are equal, set

`table[i][j][1]`

to TRUE, indicating that a single-character substring of`s1`

can be scrambled to match that of`s2`

.

**Dynamic programming:**Use nested loops to fill values in the table. Iterate over the lengths of the substrings, starting positions, and splitting positions.

For each substring length from 2 to

`n`

, for each starting position`i`

in`s1`

, and for each starting position`j`

in`s2`

, check if it’s possible to split, scramble, and match the current substrings of`s1`

and`s2`

.Set

`table[i][j][length]`

to`True`

if the scramble is possible by checking the possible splits and their combinations..

**Result:**The final result is stored in

`table[0][0][len(s1)]`

, indicating whether the entire strings`s1`

and`s2`

can be scrambled to match each other.

This can be seen in the slides below:

__Educative 99__ helps you solve complex coding problems, such as the Scramble String problem, by recognizing patterns and applying the right algorithms.

The code for this problem is as follows:

def isScramble(s1, s2):if len(s1) != len(s2):return Falsen = len(s1)table = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]# Base case for single charactersfor i in range(n):for j in range(n):if s1[i] == s2[j]:table[i][j][1] = True# Dynamic programming to fill the tablefor length in range(2, n + 1):for i in range(n - length + 1):for j in range(n - length + 1):for k in range(1, length):if (table[i][j][k] and table[i + k][j + k][length - k]) or (table[i][j + length - k][k] and table[i + k][j][length - k]):table[i][j][length] = Truebreakreturn table[0][0][len(s1)]# Driver Codedef main():# Test casestest_cases = [("great", "rgeat", True),("abcde", "caebd", False),("a", "a", True),("abc", "bca", True),("abcd", "bdac", False)]for s1, s2, expected in test_cases:result = isScramble(s1, s2)print(f"isScramble({s1}, {s2}) = {result} (expected: {expected})")if __name__ == "__main__":main()

The time complexity of the `isScramble`

function is `s1`

up to`s2`

up to

The space complexity of the `isScramble`

function is `n`

is the length of the input strings `s1`

and `s2`

. This is due to the size of the 3D table.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS