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

• 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();
}
}
}
};
``````

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