Scramble String - Naukri Code 360

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 optimisation 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 optimised approach as it might give the error of time limit exceeding 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 optimise the time and space complexity, and to check whether the string is a scrambled string or not, we will use dynamic programming.

What is a scrambled string?

A Scrambled string is a string which is obtained after swapping the sibling nodes in the binary representation of a string. We can represent a string S 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.

For e.g. We can convert node “ni” and swap its two children. It produces a scrambled string “innja”.

We basically split the string into 2 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.)

Problem Statement

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

Example

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 as R and C being adjacent is not possible.

Having understood the problem, move ahead to Coding Ninjas Studio 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 2 parts at every step, the recursion tree will be a binary tree structure.

Primary Condition

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

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 i characters of S2 should be equal to the first i characters 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 first i characters 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++
Java
Python
C#
JavaScript

C++

/* 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;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Scanner;

public class ScrambleString {

    public static boolean solveScramble(String s1, String s2) {
        if (s1.length() == 1) 
            return s1.equals(s2);

        if (s1.equals(s2)) 
            return true;

        int n = s1.length();

        for (int i = 1; i < n; i++) {
            if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
                (solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the two strings:");
        String s1 = sc.next();
        String s2 = sc.next();

        if (solveScramble(s1, s2))
            System.out.println("Yes, the string " + s2 + " is a scramble string of " + s1);
        else
            System.out.println("No, the string " + s2 + " is not a scramble string of " + s1);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def solve_scramble(s1, s2):
    if len(s1) == 1:
        return s1 == s2

    if s1 == s2:
        return True

    n = len(s1)

    for i in range(1, n):
        if (solve_scramble(s1[:i], s2[:i]) and solve_scramble(s1[i:], s2[i:])) or \
           (solve_scramble(s1[:i], s2[-i:]) and solve_scramble(s1[i:], s2[:-i])):
            return True
    return False


if __name__ == "__main__":
    s1 = input("Enter the first string: ")
    s2 = input("Enter the second string: ")

    if solve_scramble(s1, s2):
        print(f"Yes, the string {s2} is a scramble string of {s1}")
    else:
        print(f"No, the string {s2} is not a scramble string of {s1}")

You can also try this code with Online Python Compiler

Run Code

C#

using System;

class ScrambleString
{
    static bool SolveScramble(string s1, string s2)
    {
        if (s1.Length == 1)
            return s1 == s2;

        if (s1 == s2)
            return true;

        int n = s1.Length;
        bool res = false;

        for (int i = 1; i < n; i++)
        {
            if ((SolveScramble(s1.Substring(0, i), s2.Substring(0, i)) && SolveScramble(s1.Substring(i), s2.Substring(i))) ||
                (SolveScramble(s1.Substring(0, i), s2.Substring(n - i)) && SolveScramble(s1.Substring(i), s2.Substring(0, n - i))))
                return true;
        }

        return false;
    }

    static void Main()
    {
        Console.WriteLine("Enter the two strings:");
        string s1 = Console.ReadLine();
        string s2 = Console.ReadLine();

        if (SolveScramble(s1, s2))
            Console.WriteLine($"Yes, the string {s2} is a scramble string of {s1}");
        else
            Console.WriteLine($"No, the string {s2} is not a scramble string of {s1}");
    }
}

JavaScript

function solveScramble(s1, s2) {
    if (s1.length === 1) return s1 === s2;

    if (s1 === s2) return true;

    let n = s1.length;

    for (let i = 1; i < n; i++) {
        if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
            (solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
            return true;
    }
    return false;
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question('Enter the two strings:\n', (input) => {
    const [s1, s2] = input.split(" ");
    if (solveScramble(s1, s2))
        console.log(`Yes, the string ${s2} is a scramble string of ${s1}`);
    else
        console.log(`No, the string ${s2} is not a scramble string of ${s1}`);
    readline.close();
});

You can also try this code with Online Javascript Compiler

Run Code

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(2^N) where N 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(2^N).

Space Complexity

The space complexity is given by O(N) where N 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

Create a recursive function that will check if the given strings are scrambled or not.
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.
If the strings are equal, the function will always return true.
If not, we will try all possible combinations of partitioning the string by calling the function and storing the values in a map.
If the above condition meets, the function will return true, else it will return false.

Implementation

C++
Java
Python
JavaScript
C#

C++

/* 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;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.HashMap;
import java.util.Scanner;

public class ScrambleString {
    static HashMap<String, Boolean> mem = new HashMap<>();

    public static boolean solveScramble(String s1, String s2) {
        if (s1.length() == 1)
            return s1.equals(s2);

        if (s1.equals(s2))
            return true;

        String key = s1 + "*" + s2;

        if (mem.containsKey(key))
            return mem.get(key);

        int n = s1.length();

        for (int i = 1; i < n; i++) {
            if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
                (solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
            {
                mem.put(key, true);
                return true;
            }
        }
        mem.put(key, false);
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the two strings:");
        String s1 = sc.next();
        String s2 = sc.next();

        if (solveScramble(s1, s2))
            System.out.println("Yes, the string " + s2 + " is a scramble string of " + s1);
        else
            System.out.println("No, the string " + s2 + " is not a scramble string of " + s1);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

mem = {}

def solve_scramble(s1, s2):
    if len(s1) == 1:
        return s1 == s2

    if s1 == s2:
        return True

    key = s1 + "*" + s2

    if key in mem:
        return mem[key]

    n = len(s1)

    for i in range(1, n):
        if (solve_scramble(s1[:i], s2[:i]) and solve_scramble(s1[i:], s2[i:])) or \
           (solve_scramble(s1[:i], s2[-i:]) and solve_scramble(s1[i:], s2[:-i])):
            mem[key] = True
            return True
    mem[key] = False
    return False


if __name__ == "__main__":
    s1 = input("Enter the first string: ")
    s2 = input("Enter the second string: ")

    if solve_scramble(s1, s2):
        print(f"Yes, the string {s2} is a scramble string of {s1}")
    else:
        print(f"No, the string {s2} is not a scramble string of {s1}")

You can also try this code with Online Python Compiler

Run Code

JavaScript

const mem = {};

function solveScramble(s1, s2) {
    if (s1.length === 1) return s1 === s2;

    if (s1 === s2) return true;

    const key = s1 + "*" + s2;

    if (mem[key] !== undefined) return mem[key];

    let n = s1.length;

    for (let i = 1; i < n; i++) {
        if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
            (solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
        {
            return mem[key] = true;
        }
    }
    return mem[key] = false;
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question('Enter the two strings:\n', (input) => {
    const [s1, s2] = input.split(" ");
    if (solveScramble(s1, s2))
        console.log(`Yes, the string ${s2} is a scramble string of ${s1}`);
    else
        console.log(`No, the string ${s2} is not a scramble string of ${s1}`);
    readline.close();
});

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class ScrambleString
{
    static Dictionary<string, bool> mem = new Dictionary<string, bool>();

    static bool SolveScramble(string s1, string s2)
    {
        if (s1.Length == 1)
            return s1 == s2;

        if (s1 == s2)
            return true;

        string key = s1 + "*" + s2;

        if (mem.ContainsKey(key))
            return mem[key];

        int n = s1.Length;

        for (int i = 1; i < n; i++)
        {
            if ((SolveScramble(s1.Substring(0, i), s2.Substring(0, i)) && SolveScramble(s1.Substring(i), s2.Substring(i))) ||
                (SolveScramble(s1.Substring(0, i), s2.Substring(n - i)) && SolveScramble(s1.Substring(i), s2.Substring(0, n - i))))
            {
                return mem[key] = true;
            }
        }

        return mem[key] = false;
    }

    static void Main()
    {
        Console.WriteLine("Enter the two strings:");
        string s1 = Console.ReadLine();
        string s2 = Console.ReadLine();

        if (SolveScramble(s1, s2))
            Console.WriteLine($"Yes, the string {s2} is a scramble string of {s1}");
        else
            Console.WriteLine($"No, the string {s2} is not a scramble string of {s1}");
    }
}

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(N²), where N 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(N²).

Space Complexity

The space complexity of this approach is given by O(N²), where N 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(N²).

Frequently Asked Questions

What is the time complexity of scrambled string?

The time complexity of the solution done by the dynamic programming approach is given by O(N^2), where N is the length of the strings. This is because every single combination we had is computed only once.

How do you jumble strings in Python?

We can jumble strings in Python using the shuffle() function. The function is present in the ‘random’ module. But the shuffle() function takes a list as input. So we’ll first convert string to list and then, list to string again.

Conclusion

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 Coding Ninjas Studio to practice problems on dynamic programming and strings and crack your interviews like a Ninja!

Check out this article - C++ String Concatenation

Recommended problems -

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