Palindrome pair in an array of words ( or strings ) | C ++ program to check if there is a pair that of above method using Trie ; Alphabet size ( # of symbols ) ; Converts key current character into index use only ' a ' through ' z ' and lower case ; Trie node ; vector < int > pos ; To store palindromic positions in str ; isLeaf is true if the node represents end of a word ; Returns new Trie node ( initialized to NULLs ) ; 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 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ARRAY_SIZE ( a )  sizeof(a)/sizeof(a[0]) NEW_LINE #define ALPHABET_SIZE  (26) NEW_LINE #define CHAR_TO_INDEX ( c )  ((int)c - (int)'a') NEW_LINE struct TrieNode { struct TrieNode * children [ ALPHABET_SIZE ] ; int id ; bool isLeaf ; } ; struct TrieNode * getNode ( void ) { struct TrieNode * pNode = new TrieNode ; pNode -> isLeaf = false ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) pNode -> children [ i ] = NULL ; return pNode ; } bool isPalindrome ( string str , int i , int len ) { while ( i < len ) { if ( str [ i ] != str [ len ] ) return false ; i ++ , len -- ; } return true ; } void insert ( struct TrieNode * root , string key , int id ) { struct TrieNode * pCrawl = root ; for ( int level = key . length ( ) - 1 ; level >= 0 ; level -- ) { int index = CHAR_TO_INDEX ( key [ level ] ) ; if ( ! pCrawl -> children [ index ] ) pCrawl -> children [ index ] = getNode ( ) ; if ( isPalindrome ( key , 0 , level ) ) ( pCrawl -> pos ) . push_back ( id ) ; pCrawl = pCrawl -> children [ index ] ; } pCrawl -> id = id ; pCrawl -> pos . push_back ( id ) ; pCrawl -> isLeaf = true ; } void search ( struct TrieNode * root , string key , int id , vector < vector < int > > & result ) { struct TrieNode * pCrawl = root ; for ( int level = 0 ; level < key . length ( ) ; level ++ ) { int index = CHAR_TO_INDEX ( key [ level ] ) ; if ( pCrawl -> id >= 0 && pCrawl -> id != id && isPalindrome ( key , level , key . size ( ) - 1 ) ) result . push_back ( { id , pCrawl -> id } ) ; if ( ! pCrawl -> children [ index ] ) return ; pCrawl = pCrawl -> children [ index ] ; } for ( int i : pCrawl -> pos ) { if ( i == id ) continue ; result . push_back ( { id , i } ) ; } } bool checkPalindromePair ( vector < string > vect ) { struct TrieNode * root = getNode ( ) ; for ( int i = 0 ; i < vect . size ( ) ; i ++ ) insert ( root , vect [ i ] , i ) ; vector < vector < int > > result ; for ( int i = 0 ; i < vect . size ( ) ; i ++ ) { search ( root , vect [ i ] , i , result ) ; if ( result . size ( ) > 0 ) return true ; } return false ; } int main ( ) { vector < string > vect = { " geekf " , " geeks " , " or " , " keeg " , " abc " , " bc " } ; checkPalindromePair ( vect ) ? cout << " Yes " : cout << " No " ; return 0 ; }