Share my c++ solution


  • 0
    M
    class Solution {
    #define KEYT pair<string,string> 
    map<KEYT,bool> dict;
    
    bool samstr(string s1,string s2)
    {
       
    if(s1 == s2)
        return true;
    KEYT t(s1,s2);
    KEYT t2  (s2,s1);
    if(dict.find(t) != dict.end())
    {
        return dict[t];
    }
    
    
    
    int l = s1.length();
      int count[26] = {0};
        for(int i=0; i<l; i++)
        {
            count[s1[i]-'a']++;
            count[s2[i]-'a']--;
        }
    
        for(int i=0; i<26; i++)
        {
            if(count[i]!=0)
                return false;
        }
    
    for(int i =0; i< l-1;i++)
    {
        string l1 = s1.substr(0,i+1);
        string r1 = s1.substr(i+1,l-i-1);
        
        string l2 = s2.substr(0,i+1);
        string r2 = s2.substr(i+1,l-i-1);
        
        string r3 = s2.substr(0,l-i-1);
        string l3 = s2.substr(l-i-1,i+1);
        
       // cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<l3<<" "<<r3<<endl;
        
        bool same = (samstr(l1,l2) && samstr(r1,r2)) || ( samstr(l3,l1) && samstr(r3,r1));
        if(same)
        {
            dict[t] = true;
           
            dict[t2] = true;
            return true;
        }
    }
    
        dict[t] = false;
        dict[t2] = false;
        return false;
    }
    
    
    public:
    bool isScramble(string s1, string s2) {
        int l1 = s1.length();
        if(l1 == 0)
            return true;
        bool opt[l1][l1];
        for(int i = 0; i<l1;i++)
        {
            if(s1[i] == s2[i]){
            KEYT k( s1.substr(i,1), s1.substr(i,1));
            dict[k] = true;
            }
        }
       
       
        return samstr(s1,s2);
    }
    
    };

Log in to reply
 

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