Scramble String LeetCode

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.

Problem statement

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:
1. 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.
2. 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.
3. 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.

Knowledge test

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

Algorithm

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:
1. If the lengths of s1 and s2 are not equal, return FALSE as the transformation is not possible.
Table initialization:
1. 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:
1. 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:
1. Use nested loops to fill values in the table. Iterate over the lengths of the substrings, starting positions, and splitting positions.
2. 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.
3. Set table[i][j][length] to True if the scramble is possible by checking the possible splits and their combinations..
Result:
1. 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:

def isScramble(s1, s2):
    if len(s1) != len(s2):
        return False
    n = len(s1)
    table = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]
    # Base case for single characters
    for i in range(n):
        for j in range(n):
            if s1[i] == s2[j]:
                table[i][j][1] = True
    # Dynamic programming to fill the table
    for 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] = True
                        break
    return table[0][0][len(s1)]
# Driver Code
def main():
    # Test cases
    test_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()

Time complexity

The time complexity of the isScramble function is $O(n^4)$ . This is because the algorithm uses three nested loops: the outermost loop iterates over substring lengths up to $n$ , the middle loop iterates over starting positions in s1 up to $n$ , and the innermost loop iterates over starting positions in s2 up to $n$ . Additionally, there is an inner loop that iterates over possible splitting positions up to $n$ , resulting in a total of $O(n^4)$ operations.

Space complexity

The space complexity of the isScramble function is $O(n^{3})$ , where n is the length of the input strings s1 and s2. This is due to the size of the 3D table.

Free Resources