Palindrome Pairs

---

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 < word.length,
• i != j, and
• words[i] + words[j] (the concatenation of the two strings) is a palindrome.

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.

---

Try this Problem on your own or check similar problems:

1. Longest Palindromic Substring
2. Shortest Palindrome
3. Longest Palindrome by Concatenating Two Letter Words

Solution:

Java

class Solution {
    class Trie {
        public class TrieNode{
            TrieNode[] children;
            int weight;
            Set<Integer> idx;
            public TrieNode(){
                children = new TrieNode[26];
                weight = -1;
                idx = new HashSet<>();
            }
        }

        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word, int weight) {
            TrieNode iter = root;
            for (int i = word.length() - 1; i >= 0; --i) {
                char letter = word.charAt(i);
                if(iter.children[letter - 'a'] == null){
                    iter.children[letter - 'a'] = new TrieNode();
                }

                if(isPalindrome(word, 0, i)){
                    iter.idx.add(weight);
                }
                iter = iter.children[letter - 'a'];
            }
            iter.weight = weight;
            iter.idx.add(weight);
        }

        public void search(String word, int idx, List<List<Integer>> result){
            TrieNode iter = root;
            for (int i = 0; i < word.length(); ++i) {
                if(iter.weight >= 0 && iter.weight != idx && isPalindrome(word, i, word.length() - 1)){
                    result.add(List.of(idx, iter.weight));
                }
                iter = iter.children[word.charAt(i) - 'a'];
                if(iter == null) return;
            }

            for(int id: iter.idx){
                if(id != idx){
                    result.add(List.of(idx, id));
                }
            }
        }

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

    }
    Trie trie = new Trie();
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();

        for(int i = 0; i < words.length; ++i){
            trie.insert(words[i], i);
        }

        for(int i = 0; i < words.length; ++i){
            trie.search(words[i], i, result);
        }

        return result;
    }
}

JavaScript

/**
 * @param {string[]} words
 * @return {number[][]}
 */
var palindromePairs = function (words) {
  this.trie = new Trie();
  const result = [];

  for (let i = 0; i < words.length; ++i) {
    this.trie.insert(words[i], i);
  }

  for (let i = 0; i < words.length; ++i) {
    this.trie.search(words[i], i, result);
  }

  return result;
};

class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.weight = -1;
    this.idx = new Set();
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word, weight) {
    let iter = this.root;
    for (let i = word.length - 1; i >= 0; --i) {
      const letter = word.charAt(i);
      if (iter.children[letter.charCodeAt() - 97] === null) {
        iter.children[letter.charCodeAt() - 97] = new TrieNode();
      }

      if (this.isPalindrome(word, 0, i)) {
        iter.idx.add(weight);
      }
      iter = iter.children[letter.charCodeAt() - 97];
    }
    iter.weight = weight;
    iter.idx.add(weight);
  }

  search(word, idx, result) {
    let iter = this.root;
    for (let i = 0; i < word.length; ++i) {
      if (
        iter.weight >= 0 &&
        iter.weight !== idx &&
        this.isPalindrome(word, i, word.length - 1)
      ) {
        result.push([idx, iter.weight]);
      }
      iter = iter.children[word.charCodeAt(i) - 97];
      if (iter === null) return;
    }

    for (let id of iter.idx) {
      if (id !== idx) {
        result.push([idx, id]);
      }
    }
  }

  isPalindrome(s, start, end) {
    while (start < end) {
      if (s.charAt(start) !== s.charAt(end)) return false;
      ++start;
      --end;
    }
    return true;
  }
}

Python

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.weight = -1
        self.idx = set()

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word, weight):
        iter = self.root
        for i in range(len(word) - 1, -1, -1):
            letter = word[i]
            if iter.children[ord(letter) - 97] is None:
                iter.children[ord(letter) - 97] = TrieNode()

            if self.is_palindrome(word, 0, i):
                iter.idx.add(weight)
            iter = iter.children[ord(letter) - 97]
        iter.weight = weight
        iter.idx.add(weight)

    def search(self, word, idx, result):
        iter = self.root
        for i in range(len(word)):
            if iter.weight >= 0 and iter.weight != idx and self.is_palindrome(word, i, len(word) - 1):
                result.append([idx, iter.weight])
            iter = iter.children[ord(word[i]) - 97]
            if iter is None:
                return

        for id in iter.idx:
            if id != idx:
                result.append([idx, id])

    def is_palindrome(self, s, start, end):
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        self.trie = Trie()
        result = []
        for i in range(len(words)):
            self.trie.insert(words[i], i)

        for i in range(len(words)):
            self.trie.search(words[i], i, result)

        return result

C++

class TrieNode {
public:
    vector<TrieNode*> children;
    int weight;
    unordered_set<int> idx;

    TrieNode() {
        children = vector<TrieNode*>(26, nullptr);
        weight = -1;
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    void insert(const string& word, int weight) {
        TrieNode* iter = root;
        for (int i = word.length() - 1; i >= 0; --i) {
            char letter = word[i];
            if (iter->children[letter - 'a'] == nullptr) {
                iter->children[letter - 'a'] = new TrieNode();
            }

            if (isPalindrome(word, 0, i)) {
                iter->idx.insert(weight);
            }
            iter = iter->children[letter - 'a'];
        }
        iter->weight = weight;
        iter->idx.insert(weight);
    }

    void search(const string& word, int idx, vector<vector<int>>& result) {
        TrieNode* iter = root;
        for (int i = 0; i < word.length(); ++i) {
            if (iter->weight >= 0 && iter->weight != idx && isPalindrome(word, i, word.length() - 1)) {
                result.push_back({idx, iter->weight});
            }
            iter = iter->children[word[i] - 'a'];
            if (iter == nullptr) {
                return;
            }
        }

        for (int id : iter->idx) {
            if (id != idx) {
                result.push_back({idx, id});
            }
        }
    }

    bool isPalindrome(const string& s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) {
                return false;
            }
            ++start;
            --end;
        }
        return true;
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> result;
        Trie trie;

        for (int i = 0; i < words.size(); ++i) {
            trie.insert(words[i], i);
        }

        for (int i = 0; i < words.size(); ++i) {
            trie.search(words[i], i, result);
        }

        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nk^2)
• Space Complexity: O(nk)

---

Explanation:

We can utilize the implementation similar to Implement Trie (Prefix Tree) or the one where we are using set to define words indices in certain node like we did in Prefix and Suffix Search to find palindrome pairs with slight modification on insert or search as follows:

• On insert instead just inserting the word, we also check if any substring of word it's a palindrome by itself, and if it is we put the current word index/weight to the set of indices for that node. We also mark the end of word by declaring node weight to be the word index.
• On search we traverse the word in reverse order and check if the word is forming a palindrome pair with any other inserted word by checking if any of the following conditions is fulfilled:

1. First for loop checks if there is a suffix of the current word which is a palindrome and if there is another word inserted in the trie which is a reverse order of prefix of the current word prefix a + suffix String a palindrome + string b (reverse of a) (a is a our word and b is a reverse order of prefix of a and also a word in the initial set)
2. There is a prefix of some other inserted word which is a reverse order of our whole current word, with also a suffix that's a palindrome whole word a + prefix of b (palindrome) + suffix of b (reversed order of a)

When building and searching for a word we have time complexity of O(nk^2) where n is the number of words and k is the average length of the word, note that we have k^2 since we're doing k palindrome checks which take linear time complexity based on length of the word. For the space complexity we have the size of the trie which is O(nk) total number of words times the average word length. Note also that if we had a skewed trie (all words are identical) we would have k nodes the length of the word, and then for each node we would have a set of size n (all k nodes have indices of all words) leading us again to O(nk) space complexity.