Palindrome Pairs Problem

Description

LeetCode Problem 336.

Given a list of unique words, return all the pairs of thedistinct indices (i, j) in the given list, so that the concatenation of the two wordswords[i] + words[j] is a palindrome.

Example 1:

``````1
2
3
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
``````

Example 2:

``````1
2
3
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
``````

Example 3:

``````1
2
Input: words = ["a",""]
Output: [[0,1],[1,0]]
``````

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lower-case English letters.

Sample C++ Code

``````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
struct TrieNode {
TrieNode *next[26] = {};
int index = -1;
vector<int> palindromeIndexes;
};

class Solution {
TrieNode root; // Suffix trie
void add(string &s, int i) {
auto node = &root;
for (int j = s.size() - 1; j >= 0; --j) {
if (isPalindrome(s, 0, j))
// A[i]'s prefix forms a palindrome
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;
// A[i]'s prefix is empty string here, which is a palindrome.
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)
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 });
// A[i]'s prefix matches this word and A[i]'s suffix forms a palindrome
node = node->next[s[j] - 'a'];
}
if (!node) continue;
for (int j : node->palindromeIndexes) {
// A[i] is exhausted in the matching above.
// If a word whose prefix is palindrome after matching its suffix with A[i],
// then this is also a valid pair
if (i != j) ans.push_back({ i, j });
}
}
return ans;
}
};
``````