Day 84, #87, Scramble String

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
-------------------------------------------------------------
Solution #1 recursive

bool scramble(string s1,string s2) {
    if (s1 == s2) return true;    
    string t1 = s1,t2 = s2;
    sort(t1.begin(),t1.end());
    sort(t2.begin(),t2.end());
    if (t1 != t2) return false;
    
    for (int i = 1; i < s1.length(); i++) {
        string p1 = s1.substr(0,i), p2 = s1.substr(i);
        string q1 = s2.substr(0,i), q2 = s2.substr(i); 
        string q3 = s2.substr(s2.length() - i), q4 = s2.substr(0,s2.length() - i);
        
        if ((scramble(p1,q1) && scramble(p2,q2)) || (scramble(p1,q3) && scramble(p2,q4))) return true;
    }
    return false;
}

Solution #2 recursive + memo
找出s1所有的scrambled strings，然后一一对比

class Solution {
public:
    unordered_map<string,vector<string>> dic;
    void combine(vector<string> &rt,vector<string> &v1,vector<string> &v2) {
        for (string s1 : v1) {
            for (string s2 : v2) {
                rt.push_back(s1 + s2);
                rt.push_back(s2 + s1);
            }
        }
    }

    vector<string> permutation(string s) {
        vector<string> rt;
        if (s.length() == 1) {
            rt.push_back(s);
        }
    
        for (int i = 1; i < s.length(); i++) {
            string s0 = s.substr(0,i);
            string s1 = s.substr(i);
            vector<string> v1,v2; 
            if (dic.find(s0) != dic.end()) {
                v1 = dic[s0];
            }else {
                v1 = permutation(s0);
                dic[s0] = v1;   
            }
            
            if (dic.find(s1) != dic.end()) {
                v2 = dic[s1];
            }else {
                v2 = permutation(s1);
                dic[s1] = v2;
            }
            combine(rt,v1,v2);
        }
        
        return rt;
    }

    bool isScramble(string s1, string s2) {
        vector<string> rt = permutation(s1);
        for (string s : rt) {
            if (s == s2) return true;
        }
        
        return false;
    }
};

Solution #3 3-dimensional DP
dp[length][index at s1][index at s2]
int the most inner loop, delimiter breaks string in k - 1 different ways. same logic as recursive
注意loop里的终止条件

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len = s1.length();
        
        vector<vector<vector<bool> > > dp(len,vector<vector<bool> >(len,vector<bool>(len,false)));
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s1[i] == s2[j]) {
                    dp[0][i][j] = true;
                } 
            }
        }
        
        for (int k = 2; k <= len; k++) {
            for (int i = 0; i <= len - k; i++) {
                
                for (int j = 0; j <= len - k; j++) {

                    for (int delimiter = 1; delimiter < k; delimiter++) {
                        
                        if (dp[delimiter - 1][i][j] && dp[k - delimiter - 1][i + delimiter][j + delimiter]) {
                            dp[k - 1][i][j] = true;
                            break;
                        }
                            
                        if (dp[delimiter - 1][i][j + k - delimiter] && dp[k - delimiter - 1][i + delimiter][j]) {
                            dp[k - 1][i][j] = true;
                            break;
                        }
                        
                    }
                }
                
            }
            
        }
    
        return dp[len - 1][0][0];
    }
};