[help][recursive-implementation] can any good guy help me find the bug ?


  • 0

    Input:

        "abcd"    "bdac"
    

    Output:

         true    Expected:  false
    

    My code is as follows, can anyone explain me where I got wrong ? I just can not found the error !

    Code:

    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if(s1.size()!=s2.size()) 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++){
                string l1=s1.substr(0,i), r1=s1.substr(i,s1.size()-i);
                string l2=s2.substr(0,i), r2=s2.substr(i,s2.size()-i);
                string _l2=s2.substr(s2.size()-i,i), _r2=s2.substr(0, s2.size()-i);
                if(isScramble(l1, l2) && isScramble(r1, r2))
                   return true;
                if(isScramble(l1, _l2) && isScramble(r1,_r2));
                   return true;
            }
            return false;
        }
    };

  • 0

    This method can also easily cause the TLE problem


  • 0

    Dynamic solutioclass Solution

    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            /** 
             *  dp[k][i][j] means s1[i,i+k-1]   s2[j,j+k-1]   k is the length
             *  dp[1][i][j]=(s1[i]==s2[j])
             *  
             *  dp[k][i][j] = 
             *       dp[divk][i][j] && dp[k-divk][i+divk][j+divk] ||
             *       dp[divk][i][j+k-divk] && dp[k-div][i+div][j]
             *    divk : mean split the k to two parts, so divk is in (0, k)
             **/
             int len1=s1.size(), len2=s2.size();
             if(len1!=len2)  return false;
             if(s1==s2)  return true;
             /*** dp[len1+1][len1][len1] **/
             vector<vector<vector<bool>>> dp(len1+1, vector<vector<bool>>(len1, vector<bool>(len1)));
             
             for(int i=0; i<len1; i++){
                 for(int j=0; j<len1; j++){
                     dp[1][i][j]=s1[i]==s2[j];
                 }
             }
             
             for(int k=2; k<=len1; k++){
                 for(int i=0; i<len1-k+1; i++){
                     for(int j=0; j<len1-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[len1][0][0];
        }
    };

  • 0
    2
    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if(s1 == s2)  return true;
            int size_s1 = s1.size(), size_s2 = s2.size();
            if(size_s1 != size_s2)  return false;
            string ss1(s1), ss2(s2);
            /** the sorting cut edge is necessary **/ 
            sort(ss1.begin(), ss1.end());
            sort(ss2.begin(), ss2.end());
            if(ss1 != ss2)  return false;
            for(int i = 1; i < size_s1; i++) {
                string s1_sub = s1.substr(0, i);
                string s2_sub = s2.substr(0, i);
                if( (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i)))
                   ||  (isScramble(s1.substr(0, i), s2.substr(size_s1 - i, i)) && isScramble(s1.substr(i), s2.substr(0, size_s1 - i))) )
                    return true;
            }
            return false;
        }
    };**strong text**

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.