87. Scramble String - cocoder39/coco39_LC GitHub Wiki

87. Scramble String

Method 1: recursion + pruning

if s1 = AB and s2 = CD are scramble, A and C are scramble && B and D are scramble, or A and D are scramble && B and C are scramble.

tips: prune with length of string, frequency of each char.

t(n) = 2(t(1)+t(n-1)) + 2(t(2)+t(n-2)) + .. 2(t(n-1)+t(1)) = 4(t(1) + t(2) + .. t(n-1)) , thus t(n+1) = 4(t(1) + .. t(n - 1) + t(n)) = 5t(n). Hence time is O(n^5) where n is length of string

bool isScramble(string s1, string s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1 == s2) {
            return true;
        }
        
        vector<int> cnts(256);
        for (int i = 0; i < s1.length(); i++) {
            cnts[s1[i]]++;
            cnts[s2[i]]--;
        }
        for (int i = 0; i < 256; i++) {
            if (cnts[i] != 0) {
                return false;
            }
        }
        
        for (int left_len = 1, len = s1.length(); left_len <= len - 1; left_len++) {
            if (isScramble(s1.substr(0, left_len), s2.substr(0, left_len)) && 
                isScramble(s1.substr(left_len), s2.substr(left_len))) {
                return true;
            }
            if (isScramble(s1.substr(0, left_len), s2.substr(len - left_len)) && 
                isScramble(s1.substr(left_len), s2.substr(0, len - left_len))) {
                return true;
            }
        }
        return false;
    }

Method 2: DP O(n^4)

bool isScramble(string s1, string s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1 == s2) {
            return true;
        }
        
        vector<int> cnts(256);
        for (int i = 0; i < s1.length(); i++) {
            cnts[s1[i]]++;
            cnts[s2[i]]--;
        }
        for (int i = 0; i < 256; i++) {
            if (cnts[i] != 0) {
                return false;
            }
        }
        
        int len = s1.length();
        //dp[i][j][k] == true iff s1[i .. i + k - 1] and s2[j .. j + k - 1] are scramble
        vector<vector<vector<bool>>> dp(len, vector<vector<bool>>(len, vector<bool>(len + 1)));
        for (int i = 0; i < len; i++) { 
            for (int j = 0; j < len; j++) {
                dp[i][j][1] = (s1[i] == s2[j]);
            }
        }
        
        for (int l = 2; l <= len; l++) { //check dp[i][j][l]
            for (int i = 0; i + l <= len; i++) {
                for (int j = 0; j + l <= len; j++) {
                    for (int k = 1; k < l; k++) { //divide into two parts
                        if ((dp[i][j][k] && dp[i + k][j + k][l - k]) ||
                            (dp[i][j + l - k][k] && dp[i + k][j][l - k])) {
                            dp[i][j][l] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][len];
    }
⚠️ **GitHub.com Fallback** ⚠️