Share my Rolling Hash solution which can check palindrome substrings in O(1).


  • 0
    T

    I didn't see anyone else approaching the problem this way. Using Rabin-Karp like rolling hashes, with one going forward and one going reverse, we can check if the prefix is a palindrome in O(1), making each recursive call O(n), improving on the naive O(n^2) efficiency. I use two hashes to prevent spurious hits with a high probability.

    class Solution {
    public:
        int prime1 = 1093;
        int prime2 = 1187;
        int base1 = 19;
        int base2 = 13;
        vector<vector<string>> partition(string s) {
            vector<vector<string>> res;
            vector<string> partial;
            part(s, 0, res, partial);
            return res;
        }
        
        void part(string& s, int left, vector<vector<string>>& res, vector<string>& partial) {
            if(left >= s.length()) res.push_back(partial);
            int h1 = 0;
            int h2 = 0;
            int h1_r = 0;
            int h2_r = 0;
            int m1 = 1;
            int m2 = 1;
            for(int right = left; right < s.length(); right++) {
                //update hashes:
                h1_r = (h1_r*base1 + (int) s[right])%prime1;
                h2_r = (h2_r*base2 + (int) s[right])%prime2;
                h1 = (h1 + m1*((int) s[right]))%prime1;
                h2 = (h2 + m2*((int) s[right]))%prime2;
                m1*= base1;
                m2*= base2;
                m1 %= prime1;
                m2 %= prime2;
                
                if(h1 == h1_r && h2 == h2_r) {
                    //we have a palindrome!
                    partial.push_back(s.substr(left, right - left + 1));
                    part(s, right + 1, res, partial);
                    partial.pop_back();
                }
            }
        }
    };
    

Log in to reply
 

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