0336.cpp (1609B)
1 static bool isPalindrome(const string &s, int i, int j) { 2 while (i < j) { 3 if (s[i++] != s[j--]) return false; 4 } 5 6 return true; 7 } 8 9 class Trie { 10 struct Node { 11 Node *children[26] = {0}; 12 vector<int> suffix; 13 int idx = -1; 14 } root; 15 16 public: 17 void insert(const string &s, int idx) { 18 Node *crnt = &root; 19 20 for (int i = size(s) - 1; i >= 0; i--) { 21 auto &child = crnt->children[s[i] - 'a']; 22 if (!child) child = new Node(); 23 if (isPalindrome(s, 0, i)) crnt->suffix.push_back(idx); 24 25 crnt = child; 26 } 27 28 crnt->suffix.push_back(idx); 29 crnt->idx = idx; 30 } 31 32 void query(const string &s, int idx, vector<vector<int>> &res) const { 33 const Node *crnt = &root; 34 const int n = size(s); 35 36 for (int i = 0; i < n; i++) { 37 if (crnt->idx != -1 && crnt->idx != idx && isPalindrome(s, i, n - 1)) { 38 res.push_back({idx, crnt->idx}); 39 } 40 41 crnt = crnt->children[s[i] - 'a']; 42 if (!crnt) return; 43 } 44 45 for (const auto n : crnt->suffix) { 46 if (n == idx) continue; 47 res.push_back({idx, n}); 48 } 49 } 50 }; 51 52 class Solution { 53 public: 54 vector<vector<int>> palindromePairs(const vector<string> &words) const { 55 const int n = size(words); 56 vector<vector<int>> res; 57 Trie trie; 58 59 for (int i = 0; i < n; i++) 60 trie.insert(words[i], i); 61 for (int i = 0; i < n; i++) 62 trie.query(words[i], i, res); 63 64 return res; 65 } 66 };