O(sum of lengths of all words + |result|) solution


  • 0
    M

    https://github.com/MaskRay/LeetCode/blob/master/palindrome-pairs.cc

    #define REP(i, n) for (int i = 0; i < (n); i++)
    
    class Solution {
      string a;
      vector<int> z;
      void manacher(int n) {
        z.resize(n);
        z[0] = 1;
        for (int f, g = 1, i = 1; i < n; i++)
          if (i < g && z[2*f-i] != g-i)
            z[i] = min(z[2*f-i], g-i);
          else {
            g = max(g, f = i);
            for (; g < n && 2*f-g >= 0 && a[2*f-g] == a[g]; g++);
            z[f] = g-f;
          }
      }
    public:
      vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_multimap<string, int> ls, rs;
        REP(i, words.size()) {
          string &w = words[i];
          int n = w.size(), nn = 2*n+1;
          a = string(nn, '.');
          REP(j, n)
            a[2*j+1] = w[j];
          manacher(nn);
          REP(j, nn) {
            bool l = z[j] == j+1, r = j+z[j] == nn;
            if (l)
              ls.emplace(w.substr((j+z[j])/2), i);
            if (r)
              rs.emplace(w.substr(0, (j-z[j]+1)/2), i);
          }
        }
        vector<vector<int>> ret;
        REP(i, words.size()) {
          string w = words[i], ww = w;
          reverse(ww.begin(), ww.end());
          auto its = ls.equal_range(ww);
          for (auto it = its.first; it != its.second; ++it)
            if (it->second != i)
              ret.push_back(vector<int>{i, it->second});
          its = rs.equal_range(ww);
          for (auto it = its.first; it != its.second; ++it)
            if (w.size() < words[it->second].size())
              ret.push_back(vector<int>{it->second, i});
        }
        return ret;
      }
    };
    

Log in to reply
 

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