-
Notifications
You must be signed in to change notification settings - Fork 4
/
0336-palindrome-pairs.cpp
101 lines (93 loc) · 3.34 KB
/
0336-palindrome-pairs.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// class Solution {
// public:
// vector<vector<int>> palindromePairs(vector<string>& words) {
// auto is_palindrome = [&](string a) {
// int l = 0, r = a.size() - 1;
// while (l < r) {
// if (a[l] != a[r]) return false;
// l++, r--;
// }
// return true;
// };
// vector<vector<int>> res;
// for (int i = 0; i < words.size() - 1; i++) {
// auto l = words[i];
// for (int j = i + 1; j < words.size(); j++) {
// auto r = words[j];
// if (is_palindrome(l + r)) res.push_back({i, j});
// if (is_palindrome(r + l)) res.push_back({j, i});
// }
// }
// return res;
// }
// };
// class Solution {
// public:
// vector<vector<int>> palindromePairs(vector<string>& words) {
// auto is_palin = [&](string a, int l, int r) {
// while (l < r) if (a[l++] != a[r--]) return false;
// return true;
// };
// vector<vector<int>> result;
// unordered_map<string, int> d;
// for (int i = 0; i < words.size(); i++) d[words[i]] = i;
// for (int i = 0; i < words.size(); i++)
// for (int j = 0; j <= words[i].length(); j++) {
// if (is_palin(words[i], j, words[i].size() - 1)) {
// auto suff = words[i].substr(0, j);
// reverse(suff.begin(), suff.end());
// if (d.count(suff) && i != d[suff])
// result.push_back({i, d[suff]});
// }
// if (j > 0 && is_palin(words[i], 0, j - 1)) {
// auto pre = words[i].substr(j);
// reverse(pre.begin(), pre.end());
// if (d.count(pre) && d[pre] != i)
// result.push_back({d[pre], i});
// }
// }
// return result;
// }
// };
struct TrieNode {
TrieNode *next[26] = {};
int index = -1;
vector<int> palindromeIndexes;
};
class Solution {
TrieNode root;
void add(string &s, int i) {
auto node = &root;
for (int j = s.size() - 1; j >= 0; --j) {
if (isPalindrome(s, 0, j)) node->palindromeIndexes.push_back(i);
int c = s[j] - 'a';
if (!node->next[c]) node->next[c] = new TrieNode();
node = node->next[c];
}
node->index = i;
node->palindromeIndexes.push_back(i);
}
bool isPalindrome(string &s, int i, int j) {
while (i < j && s[i] == s[j]) ++i, --j;
return i >= j;
}
public:
vector<vector<int>> palindromePairs(vector<string>& A) {
int N = A.size();
for (int i = 0; i < N; ++i) add(A[i], i);
vector<vector<int>> ans;
for (int i = 0; i < N; ++i) {
auto s = A[i];
auto node = &root;
for (int j = 0; j < s.size() && node; ++j) {
if (node->index != -1 && node->index != i && isPalindrome(s, j, s.size() - 1))
ans.push_back({ i, node->index });
node = node->next[s[j] - 'a'];
}
if (!node) continue;
for (int j : node->palindromeIndexes)
if (i != j) ans.push_back({ i, j });
}
return ans;
}
};