Scrambled String

Problem Statement - link #

Given two strings S1 and S2 of equal length, the task is to determine if S2 is a scrambled form of S1.

Scrambled string: Given string str, we can represent it as a binary tree by partitioning it into two non-empty substrings recursively. Below is one possible representation of str = coder:

To scramble the string, we may choose any non-leaf node and swap its two children. Suppose, we choose the node co and swap its two children, it produces a scrambled string ocder. Similarly, if we continue to swap the children of nodes der and er, it produces a scrambled string ocred.

Note: Scrambled string is not the same as an Anagram.

Print “Yes” if S2 is a scrambled form of S1 otherwise print “No”.

Your Task:

You don’t need to read input or print anything. You only need to complete the function isScramble() which takes two strings S1 and S2 as input and returns a boolean value.

Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N*N)

Examples #

Example 1:

Input: S1="coder", S2="ocder"
Output: Yes
Explanation: ocder is a scrambled 
form of coder.

    ocder
   /    \
  oc    der
 / \    
o   c  

As "ocder" can represent it 
as a binary tree by partitioning 
it into two non-empty substrings.
We just have to swap 'o' and 'c' 
to get "coder".

Example 2:

Input: S1="abcde", S2="caebd" 
Output: No
Explanation: caebd is not a 
scrambled form of abcde.

Constraints #

• S1.length = S2.length
• S1.length <= 31
• S1 and S2 contain lower case English alphabets

Solutions #

class Solution{
    public:
    unordered_map<string, bool> m;
    bool isScramble(string S1, string S2){
        //code here
        if( S1==S2 ) return true;
        int n = S1.length();
        if( n <= 1 ) return false;
        string cur = S1 + " " + S2;
        if( m.find(cur) != m.end() ) {
            return m[cur];
        }
        bool ans = false;
        for( int i=1; i<n; i++ ) {
            if((isScramble( S1.substr(0, i), S2.substr(0, i) ) && isScramble( S1.substr(i, n-i), S2.substr(i, n-i)))
            || ((isScramble( S1.substr(0, i), S2.substr(n-i,i)) && isScramble( S1.substr(i, n-i), S2.substr(0, n-i))))) {
                ans = true;
                break;
            }
        }
        return m[cur]=ans;
    }    
};