Scramble String

Problem Statement

"Scramble String" problem states that you are given two strings. Check if the second string is a scrambled string of first one or not?

 

Explanation

Let string s = "great"

Representation of s as binary tree by recursively dividing it into two non-empty sub-strings.

 

This string can be scrambled by choosing any non leaf node and swapping it's children.

 

Therefore "rgeat" is a scrambled string of original string i.e. "great".

 

Example

s1 = "great"

 

s2 = "rgeat"

Yes

Explanation: As shown above in the images, we can see scrambling "great" results in "great". And thus the result is Yes.

s1 = "abcde"

 

s2 = "caebd"

No

 

Algorithm for Scramble String Problem

1. Initialize the two string variables s1 and s2 of the same size.

2. Create a function to check is the second string is the scrambled string of first string which accepts two string variables as it's a parameter.

3. Check if the first string is equal to the second string, return true.

4. After that, sort the first string using the inbuilt sort function.

5. Similarly, sort the second string using the inbuilt sort function.

6. Check again if the first string is not equal to the second string, return false.

7. Else create a variable scramble of the boolean type and initialize it as false.

8.

 

www.tutorialcup.com/interview/string/scramble-string.htm

Done