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:
What is the Scramble String problem in Python?
Rearranging characters in a string to form a palindrome
Splitting a string into two substrings and swapping them to match another string
Finding the longest common subsequence between two strings
A problem that involves reversing a string
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 tos2
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.