Scramble String

                            Solution in C :

static char *s_lookup, *s_s1, *s_s2;
static int s_len;

int CheckSramble(char *current, char *target, int len)
{
    char *flag=s_lookup+((current-s_s1)*s_len+target-s_s2)*s_len+len;
    if(*flag!=-1) return *flag;
    if(!memcmp(current, target, len)) return *flag=1;
    int char_table_s1_head[26]={};
    int char_table_s2_head[26]={};
    int char_table_s2_tail[26]={};
    for(int i=1;i<len;i++)
    {
        char_table_s1_head[current[i-1]-'a']++;
        char_table_s2_head[target[i-1]-'a']++;  
        if(!memcmp(char_table_s1_head, char_table_s2_head, sizeof(char_table_s1_head)))
            if(CheckSramble(current, target, i) && CheckSramble(current+i, target+i, len-i))
                return *flag=1;
        char_table_s2_tail[target[len-i]-'a']++;
        if(!memcmp(char_table_s1_head, char_table_s2_tail, sizeof(char_table_s1_head)))
            if(CheckSramble(current+i, target, len-i) && CheckSramble(current, target+len-i, i))
                return *flag=1;
    }
    return *flag=0;
}

bool isScramble(char * s1, char * s2){
    int len=strlen(s1);
    int char_table_s1[26]={};
    int char_table_s2[26]={};
    for(int i=0;i<len;i++)
    {
        char_table_s1[s1[i]-'a']++;
        char_table_s2[s2[i]-'a']++;
    }
    if(memcmp(char_table_s1, char_table_s2, sizeof(char_table_s1))) return false;
    s_len=len+1;
    s_lookup=(char*)malloc(s_len*s_len*s_len);
    memset(s_lookup, -1, s_len*s_len*s_len);
    s_s1=s1, s_s2=s2;
    bool ret=CheckSramble(s1, s2, len);
    free(s_lookup);
    return ret;
}
                        

                        Solution in C++ :

class Solution {
public:
    // checks if s2 is scrambled form of s1
    /*
        The idea is to find a position in string s1, from where scrambling must have
        started to create s2. So if k is the position, then s1[0-k] and s1[k+1, N-1]
        were the last scramble op. We do this recursively for the smaller substrings.
        
    */
    bool isScrambled(int s1_start, int s1_end, int s2_start, int s2_end,
                    string& s1, string& s2, unordered_map<string, bool>& dp) {
        // create the current position combination
        string curr_cmb = to_string(s1_start) + ',' + to_string(s1_end) + 
                            ',' + to_string(s2_start) + ',' + to_string(s2_end);
        // check if the values is in cache 
        auto it = dp.find(curr_cmb);
        if(it != dp.end())
            return dp[curr_cmb];
        
        // base cases
        if(s1_end < s1_start || s2_end < s2_start)
            return false;
        // if the size of two strings is diff, then scrambling not poss
        if(s1_end - s1_start != s2_end - s2_start)
            return false;
        // if the two substrings match, then they are scrambled
        if(s1.substr(s1_start, s1_end - s1_start + 1) == s2.substr(s2_start, s2_end - s2_start + 1))
            return true;
        
        // check if the two substrings contains the same set of chars
        vector<int> char_freq(256, 0);
        for(int i = 0; i <= s1_end - s1_start; i++)
            char_freq[s1[s1_start + i]-'a']++, char_freq[s2[s2_start + i]-'a']--;
        for(int i = 0; i < 256; i++)
            if(char_freq[i]) 
				return false;
        
        // find a position which is the potential scramble point
        for(int k = 0; k < (s1_end - s1_start); k++) {
            // check for s1[start: k], s2[start:k] and s1[k+1 : end], s2[k+1 : end]
            if(isScrambled(s1_start, s1_start + k, s2_start, s2_start + k, s1, s2, dp)  &&
              isScrambled(s1_start + k + 1, s1_end, s2_start + k + 1, s2_end, s1, s2, dp))
                return dp[curr_cmb] = true;
            // Now incase of s2, maybe scramble opertation was performed at k, so 
            // now check if the other half of s2
            // check for s1[start: k], s2[end - k : end] and s1[k+1 : end], s2[s : end - k - 1]
            if(isScrambled(s1_start, s1_start + k, s2_end - k, s2_end, s1, s2, dp)  &&
              isScrambled(s1_start + k + 1, s1_end, s2_start, s2_end - k - 1, s1, s2, dp))
                return dp[curr_cmb] = true;
        }
        return dp[curr_cmb] = false;
    }
    
    bool isScramble(string s1, string s2) {
        // DP cache: saves the result of (s1_start, s1_end, s2_start, s2_end) cmb
        unordered_map<string, bool> dp;
        return isScrambled(0, s1.size()-1, 0, s2.size()-1, s1, s2, dp);
    }
};
                    

                        Solution in Java :

public class Solution {
	public boolean isScramble(String s1, String s2) {
		if (s1.length() != s2.length()) return false;
		int len = s1.length();
		/**
		 * Let F(i, j, k) = whether the substring S1[i..i + k - 1] is a scramble of S2[j..j + k - 1] or not
		 * Since each of these substrings is a potential node in the tree, we need to check for all possible cuts.
		 * Let q be the length of a cut (hence, q < k), then we are in the following situation:
		 * 
		 * S1 [   x1    |         x2         ]
		 *    i         i + q                i + k - 1
		 * 
		 * here we have two possibilities:
		 *      
		 * S2 [   y1    |         y2         ]
		 *    j         j + q                j + k - 1
		 *    
		 * or 
		 * 
		 * S2 [       y1        |     y2     ]
		 *    j                 j + k - q    j + k - 1
		 * 
		 * which in terms of F means:
		 * 
		 * F(i, j, k) = for some 1 <= q < k we have:
		 *  (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
		 *  
		 * Base case is k = 1, where we simply need to check for S1[i] and S2[j] to be equal 
		 * */
		boolean [][][] F = new boolean[len][len][len + 1];
		for (int k = 1; k <= len; ++k)
			for (int i = 0; i + k <= len; ++i)
				for (int j = 0; j + k <= len; ++j)
					if (k == 1)
						F[i][j][k] = s1.charAt(i) == s2.charAt(j);
					else for (int q = 1; q < k && !F[i][j][k]; ++q) {
						F[i][j][k] = (F[i][j][q] && F[i + q][j + q][k - q]) || (F[i][j + k - q][q] && F[i + q][j][k - q]);
					}
		return F[0][0][len];
	}
}
                    

                        Solution in Python : 
                            
class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if s1 == s2:
            return True
        if len(s1) != len(s2):
            return False
            
        # Check both strings have same count of letters
        count1 = collections.defaultdict(int)
        count2 = collections.defaultdict(int)
        for c1, c2 in zip(s1, s2):
            count1[c1] += 1
            count2[c2] += 1
        if count1 != count2: return False
        
        # Iterate through letters and check if it results in a partition of 
        # string 1 where the collection of letters are the same
        # on the left (non-swapped) or right (swapped) sides of string 2
        # Then we recursively check these partitioned strings to see if they are scrambled
        lcount1 = collections.defaultdict(int) # s1 count from left
        lcount2 = collections.defaultdict(int) # s2 count from left
        rcount2 = collections.defaultdict(int) # s2 count from right
        for i in xrange(len(s1) - 1):
            lcount1[s1[i]] += 1          
            lcount2[s2[i]] += 1
            rcount2[s2[len(s1) - 1 - i]] += 1
            if lcount1 == lcount2:  # Left sides of both strings have same letters
                if self.isScramble(s1[:i + 1], s2[:i + 1]) and \
                   self.isScramble(s1[i + 1:], s2[i + 1:]):
                    return True
            elif lcount1 == rcount2: # Left side of s1 has same letters as right side of s2
                if self.isScramble(s1[:i + 1], s2[-(i + 1):]) and \
                   self.isScramble(s1[i + 1:], s2[:-(i + 1)]):
                    return True
        return False