Leetcode: Scramble String

 

This question is asked at Yahoo, Adobe, Apple, and Amazon. It is as follows: 

We can scramble a String, s, to get a String t using the following: 

If length of string is 1 stop. Else, Split the string into 2 non-empty substrings at random index, randomly swap/keep the substring and apply the this method recursively afterwards. This means recursively, the substrings have to be on their corresponding halves. We keep partition until string of length 1. We partition first, then merge.

great -> gr/eat

gr/eat -> gr/eat

gr/eat -> g/r e/at

g/r  /  e/at -> r/g  /   e/at

r/g   /    e/  a/t   ->  r/g   /e/   a/t 

There are several partitions in which we can described. 

First of all, the single characters will always equal a scrambled string if they are the same. The number of partition points is length of the string - 1, we need to partition all points to see if any combination of S1 results in S2. We have combinations for any partition, and we use a recursion tree to solve this. Once we keep developing and reach the leaf nodes, then we will start merging them together. For a pair of strings X,Y we can merge them into either XY or YX.

If we split the string into 2 S1 and S2, if S1 is a scrambled string and S2 is a scrambled string, then combined will be a scrambled string as well. 

MCM (matrix chain multiplications) is to find the minimum # of operations to multiply matrices. Operation call differ but recursion part the same. 

So the pseudo code for solve function is if the strings are the same and have size of 1, then we will return true. We will try all of the partitions. We'll have a flip case and no-flip case. 

So if X = X' and Y=Y' or X = P' and Y = Q' then we return true else we will go through all the possibilities. Once we have solved a subproblem, we should not try to solve it again.

class Solution {

    bool solve(string s2, string s2) {

        if(s1.size() == 1) {

            return s1 == s2;

        }

        if(s1 == s2) {

            return true;

        }

        int n = s1.size(); 

        for(int i = 1; i < n; ++i) {

            if(((solve(s1.substr(0, i), s2.substr(0, i)) and (solve(s1.substr(i), s2.substr(i))) or ((solve(s1.substr(0, i), s2.substr(n-i) and (solve(s1.substr(i), s2.substr(0, n-i)))) {

                return true;

            }

        }

        return false;

    } 

    public: 

        bool isScramble(string s1, string s2) {

            int n = s1.size();

            return solve(s1, s2);

        }

} 

All the unique characters should have the same number of frequencies. We also take an array of size 26 (number of letters in alphabet) and then find the frequency of all of the characters.

Here's the code: 

//Memoization + Pruning

class Solution {

    unordered_map<string,bool> mem;

    bool solve(string s1,string s2)

    {

        if(s1.size()==1)

            return s1==s2;

        if(s1==s2)

            return true;

        string key=s1+s2;

        if(mem.find(key)!=mem.end())

            return mem[key];

        

        //Pruning: Avoid Unnecessary recursion calls

        int n=s1.size();

        vector<int> f1(26),f2(26);

        for(int i=0;i<n;++i)

        {

            f1[s1[i]-'a']+=1;

            f2[s2[i]-'a']+=1;

        }

        if(f1!=f2)

            return mem[key]=false;

        

        bool res = false;

        for(int i=1;i<n;++i)

        {

            if((solve(s1.substr(0,i),s2.substr(0,i)) and solve(s1.substr(i),s2.substr(i)))

               or(solve(s1.substr(0,i),s2.substr(n-i)) and solve(s1.substr(i),s2.substr(0,n-i))))

                return mem[key]=true;

        }

        return mem[key]=false;

    }

public:

    bool isScramble(string s1, string s2) {

        int n = s1.size();

        return solve(s1,s2);

    }

};

The pruning avoids unnecessary recursion calls.