leetcode336 回文对

思路：

字典树。

实现：

  1 class TrieNode
  2 {
  3 public:
  4     int v[26];
  5     int id = -1;
  6     TrieNode()
  7     {
  8         fill(v, v + 26, -1); 
  9     }
 10 };
 11 TrieNode pool[1500001];
 12 class Trie
 13 {
 14 public:
 15     int root = -1;
 16     int cnt = 0;
 17     Trie()
 18     {
 19         root = cnt++;
 20     }
 21     inline void insert(string& s, int id)
 22     {
 23         int l = s.length(), cur = root;
 24         for (int i = 0; i < l; i++)
 25         {
 26             int id = s[i]-'a';
 27             if (pool[cur].v[id] == -1)
 28             {
 29                 pool[cur].v[id] = cnt++; 
 30             }
 31             cur = pool[cur].v[id];
 32         }
 33         pool[cur].id = id;
 34     }
 35     inline int search(string& s, int high, int low) // high >= low
 36     {
 37         if (s.empty() or high < low)
 38         {
 39             if (root == -1) return -1;
 40             return pool[root].id;
 41         }
 42         int l = s.length();
 43         int cur = root;
 44         for (int i = high; i >= low; i--)
 45         {
 46             int id = s[i]-'a';
 47             if (pool[cur].v[id] == -1) return -1;
 48             cur = pool[cur].v[id];
 49         }
 50         return pool[cur].id;
 51     }
 52     inline void _del(int root)
 53     {
 54         if (root < 0) return;
 55         for (int i = 0; i < 26; i++)
 56         {
 57             _del(pool[root].v[i]); 
 58             pool[root].v[i] = -1;
 59         }
 60         pool[root].id = -1;
 61     }
 62     inline void del()
 63     {
 64         _del(root);
 65     }
 66 };
 67 class Solution
 68 {
 69 public:
 70     inline bool check(string& s, int l, int r)
 71     {
 72         int x = l, y = r;
 73         while (x < y)
 74         {
 75             if (s[x] != s[y]) return false;
 76             x++; y--;
 77         }
 78         return true;
 79     }
 80     vectorint>> work(vector<string>& words)
 81     {
 82         int n = words.size();
 83         Trie* t = new Trie();
 84         vectorint>> res;
 85         for (int i = 0; i < n; i++)
 86         {
 87             t->insert(words[i], i);
 88         }
 89         vector<int> palin;
 90         for (int i = 0; i < n; i++)
 91         {
 92             int l = words[i].size();
 93             for (int j = 1; j <= l; j++)
 94             {
 95                 if (check(words[i], 0, j-1))
 96                 {
 97                     int id = t->search(words[i], l-1, j);
 98                     if (id != -1 and id != i)
 99                     {
100                         vector<int> v{id, i};
101                         res.push_back(v);
102                     }
103                 }
104                 if (check(words[i], l-j, l-1))
105                 {
106                     int id = t->search(words[i], l-j-1, 0);
107                     if (id != -1 and id != i)
108                     {
109                         vector<int> v{i, id};
110                         res.push_back(v);
111                     }
112                 }
113             }
114             int id = t->search(words[i], l-1, 0);
115             if (id != -1 and id != i)
116             {
117                 vector<int> v{i, id};
118                 res.push_back(v);
119             }
120         }
121         t->del();
122         return res; 
123     }
124 
125     vectorint>> palindromePairs(vector<string>& words)
126     {
127         vectorint>> res = work(words);
128         return res;
129     }
130 
131 };