Scramble String Solutions in C++

// Source : https://oj.leetcode.com/problems/scramble-string/
// Author : Hao Chen
// Date   : 2014-10-09



#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// The recursive way is quite simple.
//    1) break the string to two parts: 
//          s1[0..j]   s1[j+1..n]
//          s2[0..j]   s2[j+1..n]
//    2) then
//          isScramble(s1[0..j], s2[0..j]) &&  isScramble(s1[j+1..n], s2[j+1..n])
//        OR
//          isScramble(s1[0..j], s2[j+1, n]) &&  isScramble(s1[j+1..n], s2[0..j])
bool isScramble_recursion(string s1, string s2) {

    if (s1.size()!= s2.size() || s1.size()==0 || s2.size()==0) {
        return false;
    }
    if (s1 == s2){
        return true;
    } 
    string ss1 = s1;
    string ss2 = s2;
    sort(ss1.begin(), ss1.end()); 
    sort(ss2.begin(), ss2.end()); 
    if (ss1 != ss2 ) {
        return false;
    }

    for (int i=1; i<s1.size(); i++) {
        if ( isScramble_recursion(s1.substr(0,i), s2.substr(0,i)) && 
             isScramble_recursion(s1.substr(i, s1.size()-i), s2.substr(i, s2.size()-i)) ) {
            return true;
        }
        if ( isScramble_recursion(s1.substr(0,i), s2.substr(s2.size()-i, i)) && 
             isScramble_recursion(s1.substr(i, s1.size()-i), s2.substr(0, s2.size()-i)) ) {
            return true;
        }
    }

    return false;
    
}

/* 
 *  Definition
 *  
 *      dp[k][i][j] means:
 *  
 *         a) s1[i] start from 'i'
 *         b) s2[j] start from 'j'
 *         c) 'k' is the length of substring
 *  
 *  Initialization     
 *  
 *      dp[1][i][j] = (s1[i] == s2[j] ? true : false)
 *  
 *  Formula
 *  
 *      same as the above recursive method idea
 *  
 *      dp[k][i][j] = 
 *          dp[divk][i][j] && dp[k-divk][i+divk][j+divk] ||
 *          dp[divk][i][j+k-divk] && dp[k-divk][i+divk][j]
 *  
 *      `divk` mean split the k to two parts, so 0 <= divk <= k;
*/
bool isScramble_dp(string s1, string s2) {

    if (s1.size()!= s2.size() || s1.size()==0 || s2.size()==0) {
        return false;
    }
    if (s1 == s2){
        return true;
    }

    const int len = s1.size();    
    
    // dp[len+1][len][len]
    vector< vector< vector<bool> > > dp(len+1, vector< vector<bool> >(len, vector<bool>(len) ) );
   
    // ignor the k=0, just for readable code.

    // initialization k=1
    for (int i=0; i<len; i++){
        for (int j=0; j<len; j++) {
            dp[1][i][j] = (s1[i] == s2[j]);
        }
    } 
    // start from k=2 to len, O(n^4) loop. 
    for (int k=2; k<=len; k++){
        for (int i=0; i<len-k+1; i++){
            for (int j=0; j<len-k+1; j++){
                dp[k][i][j] = false;
                for (int divk = 1; divk < k && dp[k][i][j]==false; divk++){
                    dp[k][i][j] = ( dp[divk][i][j] && dp[k-divk][i+divk][j+divk] ) ||
                                  ( dp[divk][i][j+k-divk] && dp[k-divk][i+divk][j] );
                }
            }
        }
    }
    
    return dp[len][0][0];
}

bool isScramble(string s1, string s2) {

    srand(time(0));

    if (random()%2) {
        cout << "---- recursion ---" << endl;
        return isScramble_recursion(s1, s2);
    }
    cout << "---- dynamic programming ---" << endl;
    return isScramble_dp(s1, s2);
}

int main(int argc, char** argv)
{
    string s1="great", s2="rgtae";
    if (argc>2){
        s1 = argv[1];
        s2 = argv[2];
    }
    cout << s1 << ", " << s2 << endl;
    cout << isScramble(s1, s2) << endl;
    return 0;
}

#include <string>
using std::string;
#include <algorithm>

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.empty() || s2.empty() || s1.size() != s2.size()) return false;
        else if (s1 == s2) return true;
        for(auto c : s1)
            if (s2.find_first_of(c) == string::npos) return false;
            else if (std::count(s1.cbegin(), s1.cend(), c) != std::count(s2.cbegin(), s2.cend(), c)) return false;
        for (size_t i=1; i<s1.size(); ++i)
            if (isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i))) return true;
            else if (isScramble(s1.substr(0,i), s2.substr(s2.size()-i)) && isScramble(s1.substr(i), s2.substr(0, s2.size()-i))) return true;
        return false;
    }
};

/// Source : https://leetcode.com/problems/scramble-string/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

/// Recursive
/// Time Complexity: O(n^n)
/// Space Complexity: O(n^2)
class Solution {
public:
    bool isScramble(string s1, string s2) {

        if(s1.size() != s2.size())
            return false;

        if(s1 == s2)
            return true;

        unordered_map<char, int> freq;
        for(char c: s1)
            freq[c] += 1;
        for(char c: s2)
            if(freq.find(c) == freq.end())
                return false;
            else{
                freq[c] -= 1;
                if(freq[c] == 0)
                    freq.erase(c);
            }


        for(int i = 1 ; i <= s1.size() - 1 ; i ++){
            if(isScramble(s1.substr(0, i), s2.substr(0, i))
               && isScramble(s1.substr(i), s2.substr(i)))
                return true;
            if(isScramble(s1.substr(0, i), s2.substr(s2.size() - i))
               && isScramble(s1.substr(i), s2.substr(0, s2.size() - i)))
                return true;
        }

        return false;
    }
};


void print_bool(bool res){
    cout << (res ? "true" : "false") << endl;
}

int main() {

    print_bool(Solution().isScramble("great", "rgeat"));
    print_bool(Solution().isScramble("abcde", "caebd"));
    print_bool(Solution().isScramble("abcdefghijklmn", "efghijklmncadb"));

    return 0;
}

/// Source : https://leetcode.com/problems/scramble-string/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

/// Memory Search
/// Time Complexity: O(26^n)
/// Space Complexity: O(n^2)
class Solution {

public:
    bool isScramble(string s1, string s2) {

        if(s1.size() != s2.size())
            return false;

        unordered_map<string, bool> memo;
        return isScramble(s1, s2, memo);
    }

private:
    bool isScramble(string s1, string s2, unordered_map<string, bool>& memo) {

        string key = s1 + s2;
        if(memo.find(key) != memo.end())
            return memo[key];

        if(s1 == s2)
            return memo[key] = true;

        unordered_map<char, int> freq;
        for(char c: s1)
            freq[c] += 1;
        for(char c: s2)
            if(freq.find(c) == freq.end())
                return memo[key] = false;
            else{
                freq[c] -= 1;
                if(freq[c] == 0)
                    freq.erase(c);
            }

        for(int i = 1 ; i <= s1.size() - 1 ; i ++){
            if(isScramble(s1.substr(0, i), s2.substr(0, i))
               && isScramble(s1.substr(i), s2.substr(i)))
                return memo[key] = true;
            if(isScramble(s1.substr(0, i), s2.substr(s2.size() - i))
               && isScramble(s1.substr(i), s2.substr(0, s2.size() - i)))
                return memo[key] = true;
        }

        return memo[key] = false;
    }
};


void print_bool(bool res){
    cout << (res ? "true" : "false") << endl;
}

int main() {

    print_bool(Solution().isScramble("great", "rgeat"));
    print_bool(Solution().isScramble("abcde", "caebd"));
    print_bool(Solution().isScramble("abcdefghijklmn", "efghijklmncadb"));

    return 0;
}

/// Source : https://leetcode.com/problems/scramble-string/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

/// Memory Search
/// Time Complexity: O(n^4)
/// Space Complexity: O(n^4)
class Solution {

public:
    bool isScramble(string s1, string s2) {

        if(s1.size() != s2.size())
            return false;

        vector<vector<vector<int>>> memo(s1.size() + 1,
                vector<vector<int>>(s1.size(), vector<int>(s2.size(), -1))
            );
        return isScramble(s1, s2, s1.size(), 0, 0, memo);
    }

private:
    bool isScramble(string s1, string s2, int len, int i1, int i2,
                    vector<vector<vector<int>>>& memo) {

        if(memo[len][i1][i2] != -1)
            return memo[len][i1][i2];

        string a = s1.substr(i1, len);
        string b = s2.substr(i2, len);
        if(a == b)
            return memo[len][i1][i2] = true;

        unordered_map<char, int> freq;
        for(char c: a)
            freq[c] += 1;
        for(char c: b)
            if(freq.find(c) == freq.end())
                return memo[len][i1][i2] = false;
            else{
                freq[c] -= 1;
                if(freq[c] == 0)
                    freq.erase(c);
            }

        for(int i = 1 ; i <= len - 1 ; i ++){
            if(isScramble(s1, s2, i, i1, i2, memo)
               && isScramble(s1, s2, len - i, i1 + i, i2 + i, memo))
                return memo[len][i1][i2] = true;
            if(isScramble(s1, s2, i, i1, i2 + len - i, memo)
               && isScramble(s1, s2, len - i, i1 + i, i2, memo))
                return memo[len][i1][i2] = true;
        }

        return memo[len][i1][i2] = false;
    }
};


void print_bool(bool res){
    cout << (res ? "true" : "false") << endl;
}

int main() {

    print_bool(Solution().isScramble("great", "rgeat"));
    print_bool(Solution().isScramble("abcde", "caebd"));
    print_bool(Solution().isScramble("abcdefghijklmn", "efghijklmncadb"));

    return 0;
}

/// Source : https://leetcode.com/problems/scramble-string/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n^4)
/// Space Complexity: O(n^3)
class Solution {

public:
    bool isScramble(string s1, string s2) {

        if(s1.size() != s2.size())
            return false;

        vector<vector<vector<bool>>> memo(s1.size() + 1,
                                         vector<vector<bool>>(s1.size(), vector<bool>(s2.size(), false))
        );
        for(int i = 0 ; i < s1.size() ; i ++)
            for(int j = 0 ; j < s2.size() ; j ++)
                if(s1[i] == s2[j])
                    memo[1][i][j] = true;

        for(int len = 2 ; len <= s1.size() ; len ++)
            for(int i1 = 0 ; i1 <= s1.size() - len ; i1 ++)
                for(int i2 = 0 ; i2 <= s2.size() - len ; i2 ++){

                    for(int i = 1 ; i <= len - 1 ; i ++){
                        if(memo[i][i1][i2] && memo[len - i][i1 + i][i2 + i]){
                            memo[len][i1][i2] = true;
                            break;
                        }
                        else if(memo[i][i1][i2 + len - i] && memo[len - i][i1 + i][i2]){
                            memo[len][i1][i2] = true;
                            break;
                        }
                    }
                }

        return memo[s1.size()][0][0];
    }

};


void print_bool(bool res){
    cout << (res ? "true" : "false") << endl;
}

int main() {

    print_bool(Solution().isScramble("great", "rgeat"));
    print_bool(Solution().isScramble("abcde", "caebd"));
    print_bool(Solution().isScramble("abcdefghijklmn", "efghijklmncadb"));
    print_bool(Solution().isScramble("abc", "bca"));

    return 0;
}