leetcode

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 };