4ms c++ dp with pruning using primes as hash


  • 0
    P
    class Solution {
        int primes[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
    
        bool isScramble(string &s1, string &s2, int start1, int start2, int len) {
            if (s1.substr(start1,len) == s2.substr(start2,len)) return true;
            unsigned long long hash1 = 1, hash2 = 1;
            for (int i = start1;i < start1+len;++i)
                hash1 *= primes[s1[i]-'a'];
            for (int i = start2;i < start2+len;++i)
                hash2 *= primes[s2[i]-'a'];
            if (hash1 != hash2) return false;
            for (int i = 1;i <= len-1;++i) {
                if (isScramble(s1, s2, start1, start2, i) && isScramble(s1, s2, start1+i, start2+i, len-i))
                    return true;
                if (isScramble(s1, s2, start1, start2+len-i, i) && isScramble(s1, s2, start1+i, start2, len-i))
                    return true;
            }
            return false;
        }    
        
    public:
        bool isScramble(string s1, string s2) {
            return isScramble(s1, s2, 0, 0, s1.size());
        }
    };
    

Log in to reply
 

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