Scramble String

Ishita Chawla
Last Updated: May 13, 2022

Introduction

There are several problems that cannot be solved using regular algorithms like greedy or divide and conquer, or the solutions they provide are not optimal.

So, we use Dynamic Programming, which is an optimization of simple recursion to solve such problems. The basic idea is to store the results of sub-problems to avoid recalculation and reduce the time complexity of the problems.

This blog will discuss one such problem, Scramble String, which can easily be solved using recursion. This is not the optimized approach as it might give the error of time limit exceed in case of more significant constraints because of which this method is not suitable. It consumes ample time and space as it makes repetitive calls and uses a stack in the memory. So, we optimize the time and space complexity, and to check whether the string is a scrambled string or not, we will use dynamic programming.

Problem Statement

You are given strings S1 and S2, and the task is to determine whether S2 is a scrambled form of string S1 or not.

Now you may wonder what a scrambled string exactly is???

We may represent a string in the form of a binary tree by recursively dividing it into two non - empty substrings. To scramble the string, we just have to swap the 2 children of a non-leaf node. 

We basically split the string into non-empty substrings by choosing a random index of a string S and dividing it into 2 halves, say A and B.

So if we use A and B to reconstruct our original string S, there are 2 possibilities:

  • S = A + B  (Order remains same.)
  • S = B + A  (Order has been reversed.)

Example

 

  1.      S1 = “ACTIVE“

S2 = “EVITAC”

In this case, string S2 is the scrambled form of string S1.

 

In this example, we see that we can divide the word “ACTIVE” into 2 halves of length 2 and 3 and these 2 halves can also be divided into 2 halves and so on and it forms a recursive tree and in the end, we are left with leaf nodes which cannot be divided further as they have only 1 character left in them.

So now we start merging the leaf nodes in an arbitrary order to form the parent node. Now, this parent node can also merge with his sibling in any order. We can get multiple permutations of the original string using this algorithm.

 2.      S1 = “ACTOR“

S2 = “RCATO”

 

 

In this case, string S2 is not a scrambled form of S1 asand being adjacent is not possible.

Having understood the problem, move ahead to CodeStudio and first try solving the problem on your own.

Now, let us solve this problem using basic recursion, and then we will optimize our solution with the help of dynamic programming. 

Recursion 

Before we proceed with the algorithm, we need to keep in mind the following observations:

  • In the case of single characters, they have to be equal; else the strings will not be scrambled.

For example,

S1 = “A“

S2 = “A”

So, S1 and S2 are scrambled strings, but if we look at the case of:

S1 = “Z“

S2 = “A”

The strings are not scrambled. 

 

  • Now, if the length of the string is equal to N, the total number of partition points is equal to N - 1. For example,

Thus, for N = 5, the number of partitioning points = 4.          

  • Similarly, there will be N - 1 possible trees.
  • We need to try partitioning at all possible points, and check whether there exists a combination in S1 that results in string S2.
  • Since the string is divided into parts at every step, the recursion tree will be a binary tree structure. 

Primary Condition

Since we are given strings, S1 and S2, of equal length N, we have to find an index such that at least one of the following holds:

  1. S2[0. . .i - 1] is a scrambled string of S1[0. . .i-1] and S2[i . . .N - 1] is a scrambled string of S1[i . . .N - 1]. 

In other words, the first characters of S2 should be equal to the firstcharacters of S1, and the last N - i  characters of S2 should be equal to the last N - i characters of S1.

 2. S2[N - i. . . N - 1] is a scrambled string of S1[0. . .i - 1] and S2[0. . . i - 1] is a scrambled string of S1[N - i . . .N - 1]. 

In other words, the last N - i characters of S2 should be equal to the first i characters of S1 and the firstcharacters of S2 should be equal to the last N - i characters of S1.

Sounds confusing? 

Well, let us try and understand this more thoroughly.

Let the strings S1 and S2 be

S1 = “ABCDEF“

S2 = “BCDAEF”

Algorithm

  • Create a recursive function that will check if the given strings are scrambled or not.
  • If the strings are equal, the function will always return true.
  • If not, we will try all possible combinations of partitioning the string.
  • If the above condition meets, the function will return true, else it will return false.

Implementation

/* C++ program to check if two given strings are scrambled or not using recursion. */
#include <iostream>
#include <string>
using namespace std;

// Recursive function to check if the strings are scrambled.
bool solveScramble(string s1, string s2)
{
    // If the size of the string is 1, then S1 and S2 should contain the same character.
    if (s1.size() == 1)
        return s1 == s2;

    // If the strings are equal, they will definitely be scrambled strings.
    if (s1 == s2)
        return true;

    int n = s1.size();
    bool res = false;

    // Loop to check all possible combinations of the strings that can be formed.
    for (int i = 1; i < n; ++i)
    {
        // First check if S2[0..i-1] is a scrambled string of S1[0..i-1] and S2[i..n-1] is a scrambled string of S1[i..n-1].
        // If not, check if S2[n-i..n-1] is a scrambled string of S1[0..i-1] and S2[0..i-1] is a scrambled string of S1[n-i..n-1].
        // If any of the above conditions hold, the function will return true.

        if ((solveScramble(s1.substr(0, i), s2.substr(0, i)) && solveScramble(s1.substr(i), s2.substr(i))) || (solveScramble(s1.substr(0, i), s2.substr(n - i)) && solveScramble(s1.substr(i), s2.substr(0, n - i))))
            return true;
    }

    // In case none of the above conditions is satisfied, the function will return false by default.
    return false;
}

int main()
{
    string s1, s2;

    // Taking user input.
    cout << "Enter the two strings\n";
    cin >> s1 >> s2;

    // Calling the function to check the strings.
    if (solveScramble(s1, s2))
        cout << "Yes the string " << s2 << " is a scramble string of " << s1;
    else
        cout << "No, the string " << s2 << " is not a scramble string of " << s1;

    return 0;
}

Input

Enter the two strings:

active

evitac

Output

Yes, the string evitac is a scramble string of active.

Time Complexity

The time complexity of this technique is given by O(2N) where is the length of either of the 2 strings.

The function uses recursion, and in the worst case, it has to try all possible combinations. Thus, the time complexity of this technique is exponential and is given by  O(2N).

Space Complexity

The space complexity is given by O(N) where is the length of either of the 2 strings.

Since recursion uses a call stack, there will be N  calls to the function, and hence the space complexity is given by O(N). 

Dynamic Programming

Though the logic for the above approach is correct, the main problem is that of recalculations, which wastes a lot of time and space. So, an optimal approach to solve this problem is by using dynamic programming.

In this technique, we will be using a hashmap or a memoization array to store the results of the sub-problems. The rest of the logic, though, will remain the same.

Algorithm

  1. Create a recursive function that will check if the given strings are scrambled or not.
  2. We will maintain a 2-D memoization array or a simple unordered hash map of type <string, bool>, i.e., the value will either be true or false, where we will store the boolean values of substrings in an unordered map. So, if the value has occurred previously, we can get the value easily from the map, rather than calling the recursive function again.
  3. If the strings are equal, the function will always return true.
  4. If not, we will try all possible combinations of partitioning the string by calling the function and storing the values in a map.
  5. If the above condition meets, the function will return true, else it will return false.

Implementation

/* C++ program to check if two given strings are scrambled or not using top down approach of dynamic programming. */
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

// Declaring an unorderd map for memoization, i.e to store the results for subproblems.
unordered_map<string, bool> mem;

// Function to check if the strings are scrambled.
bool solveScramble(string s1, string s2)
{
    // If the size of the string is 1, then S1 and S2 should contain the same character.
    if (s1.size() == 1)
        return s1 == s2;

    // If the strings are equal, they will definitely be scrambled strings.
    if (s1 == s2)
        return true;

    // Calculating a unique map key using * operator, to avoid repetition of keys.
    string key = s1 + "*" + s2;

    // The key is returned if it is already found in the map.
    // This prevents repetition of calculations.
    if (mem.find(key) != mem.end())
        return mem[key];

    int n = s1.size();
    bool res = false;

    // Loop to check all possible combinations of the strings that can be formed.
    for (int i = 1; i < n; ++i)
    {
        // First check if S2[0..i-1] is a scrambled string of S1[0..i-1] and S2[i..n-1] is a scrambled string of S1[i..n-1].
        // If not, check if S2[n-i..n-1] is a scrambled string of S1[0..i-1] and S2[0..i-1] is a scrambled string of S1[n-i..n-1].
        // If any of the above conditions hold true, the value of the key will become true.
        // This will help in avoiding repeated calculations.
        if ((solveScramble(s1.substr(0, i), s2.substr(0, i)) and solveScramble(s1.substr(i), s2.substr(i))) or (solveScramble(s1.substr(0, i), s2.substr(n - i)) and solveScramble(s1.substr(i), s2.substr(0, n - i))))
            return mem[key] = true;
    }

    return mem[key] = false;
}
int main()
{
    string s1, s2;

    // Taking user input.
    cout << "Enter the two strings\n";
    cin >> s1 >> s2;

    // Calling the function to check the strings.
    if (solveScramble(s1, s2))
        cout << "Yes the string " << s2 << " is a scramble string of " << s1;
    else
        cout << "No, the string " << s2 << " is not a scramble string of " << s1;

    return 0;
}

Input

Enter the two strings:

actor

rcato

Output

No, the string rcato is not a scramble string of actor.

Time Complexity

The time complexity of this approach is given by O(N2), where is the length of the strings.

Since every combination is computed only once, the time complexity of this approach is given by O(N*N), or simply O(N2).

Space Complexity

The space complexity of this approach is given by O(N2), where is the length of the strings.

Since every combination will be placed in the unordered_map, the space complexity of this approach is given by O(N*N), or simply O(N2).

Key Takeaways

So, this blog discussed two different approaches to solving the problem of Scramble strings and how Dynamic Programming can enhance the flow of the normal algorithm that uses simple recursion.

To learn more, head over right now to CodeStudio to practice problems on dynamic programming and strings and crack your interviews like a Ninja!

In case of any comments or suggestions, feel free to post them in the comments section.

By Ishita Chawla

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think