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


  • 0
    B
    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;
    }

Log in to reply
 

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