# C++ O(n^2) solution using string hashing

• ``````typedef unsigned long long ull;
struct cmp{
bool operator() (const string &a, const string &b){
return a.length()<b.length();
}
};
vector<vector<int>> palindromePairs(vector<string>& words) {
map<string, int> mp;
for(int i=0; i<words.size(); ++i){
mp[words[i]]=i;
}
sort(words.begin(), words.end(), cmp());
vector<vector<int>> ans;
vector<vector<ull>> hs1(words.size(), vector<ull>()), hs2(words.size(), vector<ull>());
vector<ull> pw(1, 1);
for(int i=0; i<words.size(); ++i){
hs1[i].resize(words[i].length()+2);
hs1[i][0]=0;
for(int j=0; j<words[i].length(); ++j){
hs1[i][j+1]=hs1[i][j]*31+words[i][j]-'a'+1;
if(j+1>=pw.size())
pw.push_back(pw.back()*31);
}
hs2[i].resize(words[i].length()+2);
hs2[i][words[i].length()+1]=0;
for(int j=int(words[i].length())-1; j>=0; --j){
hs2[i][j+1]=hs2[i][j+2]*31+words[i][j]-'a'+1;
}
}
for(int i=0; i<words.size(); ++i){
for(int j=i+1; j<words.size(); ++j){
if(words[i].length()==words[j].length()){
if(hs1[i][words[i].length()]==hs2[j][1]){
vector<int> v(2, 0);
v[0]=mp[words[i]]; v[1]=mp[words[j]];
ans.push_back(v);
}
if(hs1[j][words[j].length()]==hs2[i][1]){
vector<int> v(2, 0);
v[0]=mp[words[j]]; v[1]=mp[words[i]];
ans.push_back(v);
}
}else{
int l1=words[i].length(), l2=words[j].length();
if(hs1[i][l1]==hs2[j][l2-l1+1]&&hs1[j][l2-l1]==hs2[j][1]-hs2[j][l2-l1+1]*pw[l2-l1]){
vector<int> v(2, 0);
v[0]=mp[words[i]]; v[1]=mp[words[j]];
ans.push_back(v);
}
if(hs1[j][l1]==hs2[i][min(1, l1)]&&hs1[j][l2]-hs1[j][l1]*pw[l2-l1]==hs2[j][l1+1]){
vector<int> v(2, 0);
v[0]=mp[words[j]]; v[1]=mp[words[i]];
ans.push_back(v);
}
}
}
}
return ans;
}``````

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