Palindrome Pairs

In this approach, we will concatenate each word with every other word in the list and check if the concatenated word is a palindrome or not. If the concatenated word is a palindrome, we will add the indices of this pair to the resultant list. To iterate over every pair, we will use a nested for loop.
 

Algorithm :

• Initialize a list of list ‘RESULT’.
• Iterate ‘I’ in 0 to ‘WORDS.LENGTH’:
  • Iterate ‘J’ in 0 to ‘WORDS.LENGTH’:
    • If ‘I’ equals ‘J’, check the other pairs.
  • Concatenate ‘WORDS[i]’ and WORDS’[‘J’].
  • Reverse the concatenated word.
  • If the concatenated word is equal to the reversed word, add (i, j) to ‘RESULT’.
• Return ‘RESULT’.

In this approach, we will avoid checking the pairs, which will definitely not form a pair. We will check only the following cases:

• Case 1: For any word, check if its reverse is present. If it is, we can just append the reverse at the end of the word to get a palindrome. For example, if the word is “cat”, we will check if “tac” is present or not. If it is, we can append “tac” at the end of “cat” which will result in “cattac”, which is a palindrome.
• Case 2: We will first check if the suffix is a palindrome for each suffix of a word. If it is, we will check if the reverse of the remaining prefix is present or not. If it is, we can append it at the end of the word to get a palindrome. For example, if the word is “abcdc” and a suffix is “cdc”, we will check if the reverse of “ab”, i.e. “ba” is present or not. If it is, we can append “ba” at the end of “abcdc” which will result in “abcdcba” which is a palindrome.
• Case 3:  For each prefix of a word, we will check if the prefix is a palindrome. If it is, we will check if the reverse of the suffix is present or not. If it is, we can put it at the front of the word to get a palindrome. For example, if the word is “abacd” and the prefix is “aba”, we will check if the reverse of “cd”, i.e., “dc” is present or not. If it is, we can put it at the front of “abacd” which will result in “dcabacd”, which is a palindrome.

Algorithm :

• Initialize a map ‘WORDMAP’ where the key is a word from the given list, and the value is its original index.
• Initialize a list of list ‘RESULT’.
• Iterate ‘WORD’ in ‘WORDMAP’:
  • Case 1: If the reverse of the ‘WORD’ is present in ‘WORDMAP’ and the index of the reversed word is not equal to the index of the ‘WORD’:
    • Add the indices of the pair to the ‘RESULT’.
  • Case 2: Iterate ‘SUFFIX’ in the list of all palindrome suffixes:
    • If the reverse of the ‘SUFFIX’ is present in the ‘WORDMAP’:
      • Add the indices of the pair to the result.
  • Case 3: Iterate ‘PREFIX’ in the list of all palindrome prefixes:
    • If the reverse of the ‘PREFIX’ is present in the ‘WORDMAP’:
      • Add the indices of the pair to the result.
• Return ‘RESULT’.
   

Maintain a function ‘ALLPALINDROMESUFFIXES’(‘WORD’):

• Initialize a list ‘PALINDROMESUFFIXES’.
• Iterate ‘I’ in 0 to ‘WORD.LENGTH’:
  • If WORD[‘I’, ‘WORD.LENGTH’ - 1] is a palindrome, add it to ‘PALINDROMESUFFIXES’.
• Return ‘PALINDROMESUFFIXES’.
   

Maintain a function ‘ALLPALINDROMEPREFIXES’(‘WORD’):

• Initialize a list ‘PALINDROMEPREFIXES’.
• Iterate ‘I’ in 0 to ‘WORD.LENGTH’:
  • If WORD[‘I’, ‘WORD.LENGTH’ - 1] is a palindrome, add it to ‘PALINDROMEPREFIXES’.
• Return ‘PALINDROMEPREFIXES’.

Prerequisite: Trie data structure.

In this approach, we will try to reduce the number of words to be checked for each word. We can observe that a word is a palindrome if the first and the last characters are the same, the second and second characters are the same, and so on. Using this property, we will reduce the number of words to be checked. For example, for the word ‘W’, starting with ‘a’, we only need to consider the words ending with ‘a’. This will reduce our search to words ending with ‘a’. If the second character of the word ‘W’ is ‘b’, then our search is further reduced to words ending with “ba”.

We will use a trie data structure for efficiently storing and searching words. Trie is an efficient data retrieval data structure mainly used for string manipulations. It provides a way to store strings efficiently and search for them in a lot lesser time complexity. 

Each node of the trie will have three fields:

• TrieNode[] next: Denoting the next layer of nodes.
• int index: Signifying the end of a word.
• List<Integer> list: Denoting the words of a layer.

Now, we will arrange each word from the given list into this Trie, starting from its last character, and identify the node at the next layer by indexing into the root's next array with an index equal to the difference of the ending character and 'a'. We will create a new node if the indexed node is full. We will continue to the next layer towards the beginning of the word in this manner. When we are done with the word we will update the index of the root.
 

After building up the Trie, we will start our search.   

Search(): In this method, we are going to iterate the word in the forward direction i.e, from 0th index to the last character, and check whether the root.index is greater than or equal to 0 or not. If it is greater than or equal to 0 and not minus -1(means that is the last character of the word) and it is not at the same index(because we should not combine it with itself) and is a palindrome then we will add the index of the current word and root.index to the result.

Algorithm :

• Initialize a list of list ‘RESULT’.
• Initialize a new TrieNode ‘ROOT’.
• Iterate ‘I’ in ‘WORDS.LENGTH’:
  • Add ‘WORD[‘I’] to Trie.
• Iterate ‘I’ in ‘WORDS.LENGTH’:
  • Search for palindrome pairs of ‘WORD’[‘I’].
• Return ‘RESULT’.
   

Maintain a function ‘ADD’(‘ROOT’, ‘WORD’, ‘INDEX’):

• Iterate ‘I’ in ‘WORD.LENGTH’ - 1 to 0:
  • Set ‘J’ as ‘WORD’[‘I’] - ‘a’.
  • If ‘ROOT.NEXT’[‘J’] is null, Initialize new node.
  • If ‘WORD’[0, ‘I’] is a palindrome, add ‘INDEX’ to ‘ROOT.LIST’.
  • Set ‘ROOT’ as ‘ROOT.NEXT’[‘J’] .
• Add ‘INDEX’ to ‘ROOT.LIST’.
• Set ‘ROOT.INDEX’ as ‘INDEX’.

Maintain a function ‘SEARCH’(‘WORDS’, ‘I’, ‘ROOT’, ‘RESULT’):

• Iterate ‘J’ in ‘WORD[‘I’].LENGTH’ - 1 to 0:
  • If ‘ROOT.INDEX’ is greater than or equal to 0 and not equal to ‘I’ and the substring of the current word from the index ‘J’ to ‘WORDS[‘I’].LENGTH - 1:
    • Add [‘I’, ‘ROOT.INDEX’] to ‘RESULT’.
• Set ‘ROOT’ as ‘ROOT.NEXT’[‘WORDS’[‘I’][‘J’] - 'a'].
• If ‘ROOT’ is null, return.