Palindrome pair in an array of words ( or strings ) | Java program to check if there is a pair that of above method using Trie ; Alphabet size ( # of symbols ) ; Trie node ; List < Integer > pos ; To store palindromic positions in str ; isLeaf is true if the node represents end of a word ; constructor ; Utility function to check if a string is a palindrome ; compare each character from starting with its corresponding character from last ; If not present , inserts reverse of key into Trie . If the key is prefix of a Trie node , just mark leaf node ; Start traversing word from the last ; If it is not available in Trie , then store it ; If current word is palindrome till this level , store index of current word . ; mark last node as leaf ; list to store result ; Returns true if key presents in Trie , else false ; If it is present also check upto which index it is palindrome ; If not present then return ; Function to check if a palindrome pair exists ; Construct trie ; Search for different keys ; Driver code
import java . util . ArrayList ; import java . util . Arrays ; import java . util . List ; public class Palin_pair2 { static final int ALPHABET_SIZE = 26 ; static class TrieNode { TrieNode [ ] children = new TrieNode [ ALPHABET_SIZE ] ; int id ; boolean isLeaf ; public TrieNode ( ) { isLeaf = false ; pos = new ArrayList < > ( ) ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) children [ i ] = null ; } } static boolean isPalindrome ( String str , int i , int len ) { while ( i < len ) { if ( str . charAt ( i ) != str . charAt ( len ) ) return false ; i ++ ; len -- ; } return true ; } static void insert ( TrieNode root , String key , int id ) { TrieNode pCrawl = root ; for ( int level = key . length ( ) - 1 ; level >= 0 ; level -- ) { int index = key . charAt ( level ) - ' a ' ; if ( pCrawl . children [ index ] == null ) pCrawl . children [ index ] = new TrieNode ( ) ; if ( isPalindrome ( key , 0 , level ) ) ( pCrawl . pos ) . add ( id ) ; pCrawl = pCrawl . children [ index ] ; } pCrawl . id = id ; pCrawl . pos . add ( id ) ; pCrawl . isLeaf = true ; } static List < List < Integer > > result ; static void search ( TrieNode root , String key , int id ) { TrieNode pCrawl = root ; for ( int level = 0 ; level < key . length ( ) ; level ++ ) { int index = key . charAt ( level ) - ' a ' ; if ( pCrawl . id >= 0 && pCrawl . id != id && isPalindrome ( key , level , key . length ( ) - 1 ) ) { List < Integer > l = new ArrayList < > ( ) ; l . add ( id ) ; l . add ( pCrawl . id ) ; result . add ( l ) ; } if ( pCrawl . children [ index ] == null ) return ; pCrawl = pCrawl . children [ index ] ; } for ( int i : pCrawl . pos ) { if ( i == id ) continue ; List < Integer > l = new ArrayList < > ( ) ; l . add ( id ) ; l . add ( i ) ; result . add ( l ) ; } } static boolean checkPalindromePair ( List < String > vect ) { TrieNode root = new TrieNode ( ) ; for ( int i = 0 ; i < vect . size ( ) ; i ++ ) insert ( root , vect . get ( i ) , i ) ; result = new ArrayList < > ( ) ; for ( int i = 0 ; i < vect . size ( ) ; i ++ ) { search ( root , vect . get ( i ) , i ) ; if ( result . size ( ) > 0 ) return true ; } return false ; } public static void main ( String args [ ] ) { List < String > vect = Arrays . asList ( " geekf " , " geeks " , " or " , " keeg " , " abc " , " bc " ) ; if ( checkPalindromePair ( vect ) == true ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }