<commit_before>class Solution {
    public:
        bool isScramble(string s1, string s2) {
            return helper(s1, 0, s1.size() - 1, s2, 0, s2.size()-1);
        }

        bool helper(string &s1, int start1, int end1, string &s2, int start2, int end2){
            if((end1-start1) != (end2-start2)) return false;
            int n = end1 - start1;
            bool flag = true;
            for(int i = 0; i != n; ++i){
                if(s1[start1+i] != s2[start2+i]){
                    flag = false;
                    break;
                }
            }
            if(flag == true) return true;
            for(int i = 1; i < n - 1; ++i){
                if(helper(s1, start1, start1+i, s2, start2, start2+i) && 
                        helper(s1, start1+i, end1,   s2, start2+i, end2)) return true;
                if(helper(s1, start1, start1+i, s2, start2+n-i, end2) && 
                        helper(s1, start1+i, end1,   s2, start2, start2+n-1)) return true;
            }
            return false;        
        }
};<commit_msg>add a DP solution O(n^4), accepted<commit_after>class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if(s1.size() != s2.size()) return false;
            int n = s1.size();
            vector<vector<vector<bool> > > dp(n+1,
                vector<vector<bool> >(n, vector<bool>(n, false)));
            for(int len = 1; len != n + 1; ++len){
                for(int i = 0; i != n - len + 1; ++i){
                    for(int j = 0; j != n - len + 1; ++j){
                        if(len == 1) dp[len][i][j] = (s1[i] == s2[j]);
                        else{
                            for(int k = 1; k < len; ++k){
                                if(dp[k][i][j] && dp[len-k][i+k][j+k] ||
                                   dp[k][i][j+len-k] && dp[len-k][i+k][j]){
                                    dp[len][i][j] = true;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            return dp[n][0][0];
        }
};
{'fraction_non_alphanumeric': 0.15298507462686567, 'fraction_numerical': 0.03404850746268657, 'mean_word_length': 1.0664739884393064, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7087857', 'n_tokens_mistral': 724, 'n_tokens_neox': 682, 'n_words': 162}