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, andwords[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 <= 50000 <= words[i].length <= 300words[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
add2list(node, idx);
}
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 ++) {
trie_add(root, words[i], i + 1);
}
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;
}
Input
words = ["abcd","dcba","lls","s","sssll"]
Output
[[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;
}
};
Input
words = ["abcd","dcba","lls","s","sssll"]
Output
[[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)) {
result.add(Arrays.asList(i, curr.wordEndingId));
}
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) {
result.add(Arrays.asList(i, curr.wordEndingId));
}
for (int idx : curr.palindromePrefixRemainingIds) {
result.add(Arrays.asList(i, idx));
}
}
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<>();
}
}
}
Input
words = ["bat","tab","cat"]
Output
[[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
Input
words = ["a",""]
Output
[[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;
}
}
}
Input
words = ["a",""]
Output
[[0,1],[1,0]]