## Algorithm

Problem Name: 336. Palindrome Pairs

You are given a 0-indexed array of unique strings `words`.

A palindrome pair is a pair of integers `(i, j)` such that:

• `0 <= i, j < words.length`,
• `i != j`, and
• `words[i] + words[j]` (the concatenation of the two strings) is a
.

Return an array of all the palindrome pairs of `words`.

Example 1:

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

Example 2:

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

Example 3:

```Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]
```

Constraints:

• `1 <= words.length <= 5000`
• `0 <= words[i].length <= 300`
• `words[i]` consists of lowercase English letters.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct node_s {
struct node_s *child[26];
int idx;
int *list;
int lsz;
int ln;
} node_t;
void trie_free(node_t *node) {
int i;
if (!node) return;
for (i = 0; i  <  26; i ++) {
trie_free(node->child[i]);
}
if (node->list) free(node->list);
free(node);
}
int is_palindrome(char *s, int i, int j) {
while (i  <  j) {
if (s[i] != s[j]) return 0;
i ++;
j --;
}
return 1;
}
void add2list(node_t *node, int idx) {
if (node->lsz == node->ln) {
node->lsz = !node->lsz ? 10 : node->lsz * 2;
node->list = realloc(node->list, node->lsz * sizeof(int));
//assert(node->list);
}
node->list[node->ln ++] = idx;
}
void add2p(int ***p, int *psz, int *pn, int i, int j) {
int *pair = malloc(2 * sizeof(int));
//assert(pair);
pair[0] = i;
pair[1] = j;

if (*psz == *pn) {
*psz = !*psz ? 10 : *psz * 2;
*p = realloc(*p, (*psz) * sizeof(int *));
//assert(*p);
}
(*p)[(*pn) ++] = pair;
}
void trie_add(node_t *node, char *s, int idx) {
int i, k, l;
node_t *child;

l = strlen(s);
for (i = l - 1; i >= 0; i --) {
if (is_palindrome(s, 0, i)) {  // the rest form a palindrome
}
k = s[i] - 'a';
child = node->child[k];
if (!child) {
child = calloc(1, sizeof(node_t));
//assert(child);
node->child[k] = child;
}
node = child;
}
node->idx = idx;  // mark the end of the word
}
void trie_search(node_t *node, char *s, int l, int idx, int ***p, int *psz, int *pn) {
int i, k;
for (i = 0; i  <  l; i ++) {
if (node->idx && node->idx != idx && is_palindrome(s, i, l - 1)) {
add2p(p, psz, pn, idx - 1, node->idx - 1);
}
node = node->child[s[i] - 'a'];
if (!node) return;
}
if (node->idx && node->idx != idx) {  // both words end and match
add2p(p, psz, pn, idx - 1, node->idx - 1);
}
for (i = 0; i  <  node->ln; i ++) {  // the rest of words
k = node->list[i];
if (k != idx) {
add2p(p, psz, pn, idx - 1, k - 1);
}
}
}
int** palindromePairs(char** words, int wordsSize, int** columnSizes, int* returnSize) {
int **p, psz, pn;
int i, j;
node_t *root;
char *s;

root = calloc(1, sizeof(node_t));
//assert(root);

// build the trie
for (i = 0; i  <  wordsSize; i ++) {
}

psz = 100;
pn = 0;
p = malloc(psz * sizeof(int *));
//assert(p);

// search the trie
for (i = 0; i  <  wordsSize; i ++) {
s = words[i];
trie_search(root, s, strlen(s), i + 1, &p, &psz, &pn);
}

trie_free(root);

if (pn) {
*columnSizes = malloc(pn * sizeof(int));
//assert(*columnSizes);
for (i = 0; i  <  pn; i ++) {
(*columnSizes)[i] = 2;
}
} else {
free(p);
p = NULL;
}

*returnSize = pn;
return p;
}
``````
Copy The Code &

Input

cmd
words = ["abcd","dcba","lls","s","sssll"]

Output

cmd
[[0,1],[1,0],[3,2],[2,4]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<vector<int>> palindromePairs(vector < string>& words) {
vector<vector<int>>res;
buildTrie(words);
for(int i = 0; i  <  words.size(); i++){
string s = words[i];
for(auto x: Trie[s]) if(isPalindrome(x.first) && i != x.second) res.push_back({i, x.second});
for(int j = 0; j <= s.size(); j++)
if(m.count(s.substr(0, j)) && isPalindrome(s.substr(j)) && i != m[s.substr(0, j)])
res.push_back({i, m[s.substr(0, j)]}>;
}
return res;
}

private:
unordered_map < string, vector<pair > >Trie;
unordered_mapm;
void buildTrie(vector < string>& words){
for(int i = 0; i < words.size(); i++){
string s = words[i];
reverse(s.begin(), s.end());
m[s] = i;
for(int j = 0; j  <  s.size(); j++) Trie[s.substr(0, j)].push_back({s.substr(j), i});
}
}

bool isPalindrome(string s){
int i = 0, j = s.size() - 1;
while(i  <  j) if(s[i++] != s[j--]) return false;
return true;
}
};
``````
Copy The Code &

Input

cmd
words = ["abcd","dcba","lls","s","sssll"]

Output

cmd
[[0,1],[1,0],[3,2],[2,4]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
for (int i = 0; i  <  words.length; i++) {
String word = words[i];
TrieNode curr = root;
for (int j = 0; j  <  word.length(); j++) {
if (curr.wordEndingId != -1 && isPalindrome(word, j)) {
}
char c = word.charAt(j);
curr = curr.children.get(c);
if (curr == null) {
break;
}
}
if (curr == null) {
continue;
}
if (curr.wordEndingId != -1 && curr.wordEndingId != i) {
}
for (int idx : curr.palindromePrefixRemainingIds) {
}
}
return result;
}

private static boolean isPalindrome(String s, int start) {
int end = s.length() - 1;
while (start  <  end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}

private static class TrieNode {
private int wordEndingId;
private Map < Character, TrieNode> children;
private List palindromePrefixRemainingIds;

public TrieNode() {
this.wordEndingId = -1;
this.children = new HashMap < >();
this.palindromePrefixRemainingIds = new ArrayList<>();
}
}
}
``````
Copy The Code &

Input

cmd
words = ["bat","tab","cat"]

Output

cmd
[[0,1],[1,0]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def palindromePairs(self, words):
index, res = {w:i for i, w in enumerate(words)}, []
for i, w in enumerate(words):
for j in range(len(w) + 1):
pre, suf = w[:j], w[j:]
if pre == pre[::-1]:
suf = suf[::-1]
if suf != w and suf in index:
res.append([index[suf], i])
if j != len(w) and suf == suf[::-1]:
pre = pre[::-1]
if pre != w and pre in index:
res.append([i, index[pre]])
return res
``````
Copy The Code &

Input

cmd
words = ["a",""]

Output

cmd
[[0,1],[1,0]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
public class _0336_PalindromePairs
{
public IList < IList<int>> PalindromePairs(string[] words)
{
if (words == null || words.Length  <  2) return new List();
for (int i = 0; i  <  words.Length; i++) map.Add(words[i], i);

for (int i = 0; i  <  words.Length; i++)
{
if (string.IsNullOrEmpty(words[i])) continue;

for (int j = 0; j  < = words[i].Length; j++)
{
var prefix = words[i].Substring(0, j);
var surfix = words[i].Substring(j);

if (IsPalindrome(prefix))
{
var surfixReverse = ReverseString(surfix);
if (map.ContainsKey(surfixReverse) && map[surfixReverse] != i)
result.Add(new List < int>() { map[surfixReverse], i });
}
if (IsPalindrome(surfix))
{
var prefixReverse = ReverseString(prefix);
if (map.ContainsKey(prefixReverse) && map[prefixReverse] != i && !string.IsNullOrEmpty(surfix))
result.Add(new List < int>() { i, map[prefixReverse] });
}
}
}
return new List= 0; i--)
sb.Append(str[i]);

return sb.ToString();
}

private bool IsPalindrome(string str)
{
int left = 0, right = str.Length - 1;
while (left  < = right)
if (str[left++] != str[right--]) return false;

return true;
}
}
}
``````
Copy The Code &

Input

cmd
words = ["a",""]

Output

cmd
[[0,1],[1,0]]