Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Example 2:
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
Related Topics:
Hash Table, String, Trie
Similar Questions:
// OJ: https://leetcode.com/problems/palindrome-pairs/
// Author: github.com/lzl124631x
// Time: O(N * L^2)
// Space: O(NL)
// Ref: https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure
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)) node->palindromeIndexes.push_back(i); // A[i]'s prefix forms a palindrome
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); // A[i]'s prefix is empty string here, which is a palindrome.
}
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 }); // 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;
}
};