leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0336.cpp (1609B)

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