Palindrome pair in an array of words (or strings)

Last Updated : 13 Sep, 2023

Given a list of words, find if any of the two words can be joined to form a palindrome.

Examples:

Input  : list[] = {"geekf", "geeks", "or", 
                            "keeg", "abc", "bc"}
Output : Yes
There is a pair "geekf" and "keeg"

Input : list[] =  {"abc", "xyxcba", "geekst", "or",
                                      "keeg", "bc"}
Output : Yes
There is a pair "abc" and "xyxcba"

Asked in : Google Interview

Simple approach:

1- Consider each pair one by one.
2- Check if any of the pairs forms a palindrome
   after concatenating them.
3- Return true, if any such pair exists.
4- Else, return false.

Implementation:

C++

// C++ program to find if there is a pair that 
// can form a palindrome. 
#include<bits/stdc++.h> 
using namespace std; 
  
// Utility function to check if a string is a 
// palindrome 
bool isPalindrome(string str) 
{ 
    int len = str.length(); 
  
    // compare each character from starting 
    // with its corresponding character from last 
    for (int i = 0; i < len/2; i++ ) 
        if (str[i] != str[len-i-1]) 
            return false; 
  
    return true; 
} 
  
// Function to check if a palindrome pair exists 
bool checkPalindromePair(vector <string> vect) 
{ 
    // Consider each pair one by one 
    for (int i = 0; i< vect.size()-1; i++) 
    { 
        for (int j = i+1; j< vect.size() ; j++) 
        { 
            string check_str; 
  
            // concatenate both strings 
            check_str = vect[i] + vect[j]; 
  
            // check if the concatenated string is 
            // palindrome 
            if (isPalindrome(check_str)) 
                return true; 
  
            // check for other combination of the two strings 
            check_str = vect[j] + vect[i]; 
            if (isPalindrome(check_str)) 
                return true; 
        } 
    } 
    return false; 
} 
  
// Driver code 
int main() 
{ 
    vector <string> vect = {"geekf", "geeks", "or", 
                            "keeg", "abc", "bc"}; 
  
  
    checkPalindromePair(vect)? cout << "Yes" : 
                               cout << "No"; 
    return 0; 
} 

Java

// Java program to find if there is a pair that 
// can form a palindrome. 
import java.util.Arrays; 
import java.util.List; 
public class Palin_pair1 { 
          
    // Utility function to check if a string is a 
    // palindrome 
    static boolean isPalindrome(String str) 
    { 
        int len = str.length(); 
       
        // compare each character from starting 
        // with its corresponding character from last 
        for (int i = 0; i < len/2; i++ ) 
            if (str.charAt(i) != str.charAt(len-i-1)) 
                return false; 
       
        return true; 
    } 
       
    // Function to check if a palindrome pair exists 
    static boolean checkPalindromePair(List<String> vect) 
    { 
        // Consider each pair one by one 
        for (int i = 0; i< vect.size()-1; i++) 
        { 
            for (int j = i+1; j< vect.size() ; j++) 
            { 
                String check_str = ""; 
       
                // concatenate both strings 
                check_str = check_str + vect.get(i) + vect.get(j); 
       
                // check if the concatenated string is 
                // palindrome 
                if (isPalindrome(check_str)) 
                    return true; 
  
                check_str = vect.get(j) + vect.get(i); 
       
                // check if the concatenated string is 
                // palindrome 
                if (isPalindrome(check_str)) 
                    return true; 
            } 
        } 
        return false; 
    } 
       
    // Driver code 
    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"); 
    } 
} 
//This code is contributed by Sumit Ghosh 

Python3

# Python3 program to find if  
# there is a pair that 
# can form a palindrome. 
  
# Utility function to check  
# if a string is a palindrome 
def isPalindrome(st): 
  
    length = len(st) 
  
    # Compare each character  
    # from starting with its  
    # corresponding character from last 
    for i in range(length // 2): 
        if (st[i] != st[length - i - 1]): 
            return False
  
    return True
  
# Function to check if a  
# palindrome pair exists 
def checkPalindromePair(vect): 
  
    # Consider each pair one by one 
    for i in range(len(vect) - 1): 
        for j in range(i + 1, len(vect)): 
              
            # Concatenate both strings 
            check_str = vect[i] + vect[j] 
  
            # Check if the concatenated  
            # string is palindrome 
            if (isPalindrome(check_str)): 
                return True
  
            # Check for other combination  
            # of the two strings 
            check_str = vect[j] + vect[i] 
            if (isPalindrome(check_str)): 
                return True
    return False
    
# Driver code 
if __name__ == "__main__": 
    
    vect = ["geekf", "geeks", "or", 
            "keeg", "abc", "bc"] 
      
    if checkPalindromePair(vect): 
        print("Yes") 
    else: 
        print ("No") 
    
# This code is contributed by Chitranayal

C#

// C# program to find if there is a pair that 
// can form a palindrome. 
using System; 
using System.Collections.Generic; 
  
class GFG  
{ 
          
    // Utility function to check if  
    // a string is a palindrome 
    static Boolean isPalindrome(String str) 
    { 
        int len = str.Length; 
      
        // compare each character from starting 
        // with its corresponding character from last 
        for (int i = 0; i < len / 2; i++ ) 
            if (str[i] != str[len - i - 1]) 
                return false; 
      
        return true; 
    } 
      
    // Function to check if a palindrome pair exists 
    static Boolean checkPalindromePair(List<String> vect) 
    { 
        // Consider each pair one by one 
        for (int i = 0; i< vect.Count - 1; i++) 
        { 
            for (int j = i + 1; j< vect.Count ; j++) 
            { 
                String check_str = ""; 
      
                // concatenate both strings 
                check_str = check_str + vect[i] + vect[j]; 
      
                // check if the concatenated string is 
                // palindrome 
                if (isPalindrome(check_str)) 
                    return true; 
  
                check_str = vect[j] + vect[j]; 
      
                // check if the concatenated string is 
                // palindrome 
                if (isPalindrome(check_str)) 
                    return true; 
            } 
        } 
        return false; 
    } 
      
    // Driver code 
    public static void Main(String []args) 
    { 
        List<String> vect = new List<String>(){"geekf", "geeks", "or", 
                                                  "keeg", "abc", "bc"}; 
      
      
        if (checkPalindromePair(vect) == true) 
            Console.WriteLine("Yes"); 
        else
            Console.WriteLine("No"); 
    } 
} 
  
// This code is contributed by Rajput-Ji 

Javascript

<script> 
  
// Javascript program to find if there  
// is a pair that can form a palindrome. 
  
// Utility function to check if a  
// string is a palindrome 
function isPalindrome(str) 
{ 
    let len = str.length; 
    
    // Compare each character from starting 
    // with its corresponding character from last 
    for(let i = 0; i < len / 2; i++ ) 
        if (str[i] != str[len - i - 1]) 
            return false; 
    
    return true; 
} 
  
// Function to check if a palindrome pair exists 
function checkPalindromePair(vect) 
{ 
      
    // Consider each pair one by one 
    for(let i = 0; i < vect.length - 1; i++) 
    { 
        for(let j = i + 1; j < vect.length; j++) 
        { 
            let check_str = ""; 
    
            // Concatenate both strings 
            check_str = check_str + vect[i] + vect[j]; 
    
            // Check if the concatenated string is 
            // palindrome 
            if (isPalindrome(check_str)) 
                return true; 
  
            check_str = vect[j] + vect[i]; 
    
            // Check if the concatenated string is 
            // palindrome 
            if (isPalindrome(check_str)) 
                return true; 
        } 
    } 
    return false; 
} 
  
// Driver code 
let vect = [ "geekf", "geeks", "or", 
             "keeg", "abc", "bc" ] 
               
if (checkPalindromePair(vect) == true) 
    document.write("Yes"); 
else   
    document.write("No"); 
  
// This code is contributed by rag2127 
  
</script> 

Output

Yes

Time Complexity : O(n²k)
Here n is the number of words in the list and k is the maximum length that is checked for a palindrome.

Auxiliary Space : O(1)

Efficient method:

It can be done efficiently by using the Trie data structure. The idea is to maintain a Trie of the reverse of all words.

1) Create an empty Trie.
2) Do following for every word:-
    a) Insert reverse of current word.
    b) Also store up to which index it is 
       a palindrome.
3) Traverse list of words again and do following 
   for every word.
    a) If it is available in Trie then return true
    b) If it is partially available
         Check the remaining word is palindrome or not 
         If yes then return true that means a pair
         forms a palindrome.
         Note: Position upto which the word is palindrome
               is stored because of these type of cases.

C++

// C++ program to check if there is a pair that 
// of above method using Trie 
#include<bits/stdc++.h> 
using namespace std; 
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 
  
// Alphabet size (# of symbols) 
#define ALPHABET_SIZE (26) 
  
// Converts key current character into index 
// use only 'a' through 'z' and lower case 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 
  
// Trie node 
struct TrieNode 
{ 
    struct TrieNode *children[ALPHABET_SIZE]; 
    vector<int> pos; // To store palindromic 
                     // positions in str 
    int id; 
  
    // isLeaf is true if the node represents 
    // end of a word 
    bool isLeaf; 
}; 
  
// Returns new Trie node (initialized to NULLs) 
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; 
} 
  
// Utility function to check if a string is a 
// palindrome 
bool isPalindrome(string str, int i, int len) 
{ 
    // compare each character from starting 
    // with its corresponding character from last 
    while (i < len) 
    { 
        if (str[i] != str[len]) 
            return false; 
        i++, len--; 
    } 
  
    return true; 
} 
  
// If not present, inserts reverse of key into Trie. If  
// the key is prefix of a Trie node, just mark leaf node 
void insert(struct TrieNode* root, string key, int id) 
{ 
    struct TrieNode *pCrawl = root; 
  
    // Start traversing word from the last 
    for (int level = key.length()-1; level >=0; level--) 
    { 
        // If it is not available in Trie, then 
        // store it 
        int index = CHAR_TO_INDEX(key[level]); 
        if (!pCrawl->children[index]) 
            pCrawl->children[index] = getNode(); 
  
        // If current word is palindrome till this 
        // level, store index of current word. 
        if (isPalindrome(key, 0, level)) 
            (pCrawl->pos).push_back(id); 
  
        pCrawl = pCrawl->children[index]; 
    } 
    pCrawl->id = id; 
    pCrawl->pos.push_back(id); 
  
    // mark last node as leaf 
    pCrawl->isLeaf = true; 
} 
  
// Returns true if key presents in Trie, else false 
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 it is present also check upto which index 
        // it is palindrome 
        if (pCrawl->id >= 0 && pCrawl->id != id && 
            isPalindrome(key, level, key.size()-1)) 
            result.push_back({id, pCrawl->id}); 
  
        // If not present then return 
        if (!pCrawl->children[index]) 
            return; 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    for (int i: pCrawl->pos) 
    { 
        if (i == id) 
            continue; 
        result.push_back({id, i}); 
    } 
} 
  
// Function to check if a palindrome pair exists 
bool checkPalindromePair(vector <string> vect) 
{ 
    // Construct trie 
    struct TrieNode *root = getNode(); 
    for (int i = 0; i < vect.size(); i++) 
        insert(root, vect[i], i); 
  
    // Search for different keys 
    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; 
} 
  
// Driver code 
int main() 
{ 
    vector <string> vect = {"geekf", "geeks", "or", 
                            "keeg", "abc", "bc"}; 
  
  
    checkPalindromePair(vect)? cout << "Yes" : 
                               cout << "No"; 
    return 0; 
} 

Java

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

Python3

from typing import List
  
# Trie node class 
class TrieNode: 
    # Constructor 
    def __init__(self): 
        self.children = [None]*26
        self.pos = []  # To store palindromic positions in str 
        self.id = None
        self.isLeaf = False  # isLeaf is True if the node represents end of a word 
  
# Utility function to check if a string is a palindrome 
def isPalindrome(s: str, i: int, j: int) -> bool: 
    
    # Compare each character from starting with 
    # its corresponding character from last 
    while i < j: 
        if s[i] != s[j]: 
            return False
        i += 1
        j -= 1
    return True
  
# If not present, inserts reverse of key into Trie. If the key is prefix of a Trie node, just mark leaf node 
def insert(root: TrieNode, key: str, id: int) -> None: 
    pCrawl = root 
  
    # Start traversing word from the last 
    for level in range(len(key)-1, -1, -1): 
        # If it is not available in Trie, then store it 
        index = ord(key[level]) - ord('a') 
        if not pCrawl.children[index]: 
            pCrawl.children[index] = TrieNode() 
  
        # If current word is palindrome till this level, store index of current word. 
        if isPalindrome(key, 0, level): 
            pCrawl.pos.append(id) 
  
        pCrawl = pCrawl.children[index] 
    pCrawl.id = id
    pCrawl.pos.append(id) 
  
    # Mark last node as leaf 
    pCrawl.isLeaf = True
  
# Returns true if key presents in Trie, else false 
def search(root: TrieNode, key: str, id: int) -> None: 
    pCrawl = root 
    for level in range(len(key)): 
        index = ord(key[level]) - ord('a') 
  
        # If it is present also check up to which index it is palindrome 
        if pCrawl.id is not None and pCrawl.id != id and isPalindrome(key, level, len(key)-1): 
            l = [id, pCrawl.id] 
            result.append(l) 
  
        # If not present then return 
        if not pCrawl.children[index]: 
            return
  
        pCrawl = pCrawl.children[index] 
  
    for i in pCrawl.pos: 
        if i == id: 
            continue
        l = [id, i] 
        result.append(l) 
  
# Function to check if a palindrome pair exists 
def checkPalindromePair(vect: List[str]) -> bool: 
    # Construct Trie 
    root = TrieNode() 
    for i in range(len(vect)): 
        insert(root, vect[i], i) 
  
    # Search for different keys 
    global result 
    result = [] 
    for i in range(len(vect)): 
        search(root, vect[i], i) 
  
        if len(result) > 0: 
            return True
  
    return False
  
# Driver code 
vect = ["geekf", "geeks", "or", "keeg", "abc", "bc"] 
  
if checkPalindromePair(vect) == True: 
    print("Yes") 
else: 
    print("No") 

C#

// C# program to check if there is  
// a pair that of above method using Trie 
using System; 
using System.Collections.Generic; 
  
class GFG 
{ 
  
    // Alphabet size (# of symbols) 
    static readonly int ALPHABET_SIZE = 26; 
  
    // Trie node 
    class TrieNode 
    { 
        public TrieNode[] children = new TrieNode[ALPHABET_SIZE]; 
        public List<int> pos; // To store palindromic 
                              // positions in str 
        public int id; 
  
        // isLeaf is true if the node  
        // represents end of a word 
        public Boolean isLeaf; 
  
        // constructor 
        public TrieNode() 
        { 
            isLeaf = false; 
            pos = new List<int>(); 
            for (int i = 0; i < ALPHABET_SIZE; i++) 
                children[i] = null; 
        } 
    } 
  
    // Utility function to check if  
    // a string is a palindrome 
    static Boolean isPalindrome(String str,  
                                int i, int len)  
    { 
        // compare each character from starting 
        // with its corresponding character from last 
        while (i < len)  
        { 
            if (str[i] != str[len]) 
                return false; 
  
            i++; 
            len--; 
        } 
        return true; 
    } 
  
    // If not present, inserts reverse of  
    // key into Trie. If the key is prefix of 
    // a Trie node, just mark leaf node 
    static void insert(TrieNode root,  
                       String key, int id) 
    { 
        TrieNode pCrawl = root; 
  
        // Start traversing word from the last 
        for (int level = key.Length - 1; 
                 level >= 0; level--)  
        { 
            // If it is not available in Trie,  
            // then store it 
            int index = key[level] - 'a'; 
            if (pCrawl.children[index] == null) 
                pCrawl.children[index] = new TrieNode(); 
  
            // If current word is palindrome till this 
            // level, store index of current word. 
            if (isPalindrome(key, 0, level)) 
                (pCrawl.pos).Add(id); 
  
            pCrawl = pCrawl.children[index]; 
        } 
        pCrawl.id = id; 
        pCrawl.pos.Add(id); 
  
        // mark last node as leaf 
        pCrawl.isLeaf = true; 
    } 
  
    // list to store result  
    static List<List<int>> result; 
  
    // Returns true if key presents  
    // in Trie, else false 
    static void search(TrieNode root,  
                       String key, int id)  
    { 
        TrieNode pCrawl = root; 
        for (int level = 0;  
                 level < key.Length; level++)  
        { 
            int index = key[level] - 'a'; 
  
            // If it is present also check  
            // upto which index it is palindrome 
            if (pCrawl.id >= 0 && pCrawl.id != id &&  
                isPalindrome(key, level, key.Length - 1))  
            { 
                List<int> l = new List<int>(); 
                l.Add(id); 
                l.Add(pCrawl.id); 
                result.Add(l); 
            } 
  
            // If not present then return 
            if (pCrawl.children[index] == null) 
                return; 
  
            pCrawl = pCrawl.children[index]; 
        } 
  
        foreach (int i in pCrawl.pos) 
        { 
            if (i == id) 
                continue; 
            List<int> l = new List<int>(); 
            l.Add(id); 
            l.Add(i); 
            result.Add(l); 
        } 
    } 
  
    // Function to check if a palindrome pair exists 
    static Boolean checkPalindromePair(List<String> vect) 
    { 
          
        // Construct trie 
        TrieNode root = new TrieNode(); 
        for (int i = 0; i < vect.Count; i++) 
            insert(root, vect[i], i); 
  
        // Search for different keys 
        result = new List<List<int>>(); 
        for (int i = 0; i < vect.Count; i++) 
        { 
            search(root, vect[i], i); 
  
            if (result.Count > 0) 
                return true; 
        } 
        return false; 
    } 
  
    // Driver code 
    public static void Main(String []args)  
    { 
        List<String> vect = new List<String>(){"geekf", "geeks",  
                                               "or", "keeg",  
                                               "abc", "bc"}; 
  
        if (checkPalindromePair(vect) == true) 
            Console.WriteLine("Yes"); 
        else
            Console.WriteLine("No"); 
    } 
} 
  
// This code is contributed by Rajput-Ji 

Javascript

// JavaScript program to check if there is a pair that 
// of above method using Trie 
const ALPHABET_SIZE = 26; 
  
// Converts key current character into index 
// use only 'a' through 'z' and lower case 
function CHAR_TO_INDEX(c) { 
    return c.charCodeAt() - 'a'.charCodeAt(); 
} 
  
// Trie node 
class TrieNode { 
  constructor() { 
    this.children = new Array(ALPHABET_SIZE).fill(null); 
    this.pos = []; // To store palindromic positions in str 
    this.id = -1; 
      
    // isLeaf is true if the node represents end of a word 
    this.isLeaf = false; 
  } 
} 
  
// Returns new Trie node (initialized to NULLs) 
function getNode() { 
  const pNode = new TrieNode(); 
  return pNode; 
} 
  
// Utility function to check if a string is a palindrome 
function isPalindrome(str, i, len) { 
  while (i < len) { 
    if (str[i] != str[len]) 
        return false; 
    i++, len--; 
  } 
  return true; 
} 
  
// If not present, inserts reverse of key into Trie. If 
// the key is prefix of a Trie node, just mark leaf node 
function insert(root, key, id) { 
  
  let pCrawl = root; 
    
  // Start traversing word from the last 
  for (let level = key.length - 1; level >= 0; level--) { 
    
      // If it is not available in Trie, then store it 
    const index = CHAR_TO_INDEX(key[level]); 
      
    if (!pCrawl.children[index]) 
        pCrawl.children[index] = getNode(); 
  
    // If current word is palindrome till this level, store index of current word. 
    if (isPalindrome(key, 0, level)) 
         pCrawl.pos.push(id); 
  
    pCrawl = pCrawl.children[index]; 
  } 
  pCrawl.id = id; 
  pCrawl.pos.push(id); 
    
  // mark last node as leaf 
  pCrawl.isLeaf = true; 
  
} 
  
// Returns true if key presents in Trie, else false 
function search(root, key, id, result) { 
  
  let pCrawl = root; 
    
  for (let level = 0; level < key.length; level++) { 
    
    const index = CHAR_TO_INDEX(key[level]); 
  
      // If it is present also check upto which index it is palindrome 
      if (pCrawl.id >= 0 && pCrawl.id != id && isPalindrome(key, level, key.length - 1)) 
          result.push([id, pCrawl.id]); 
  
      // If not present then return 
      if (!pCrawl.children[index]) 
          return; 
  
      pCrawl = pCrawl.children[index]; 
  } 
  
  for (let i of pCrawl.pos) { 
      if (i == id) 
          continue; 
      result.push([id, i]); 
  } 
  
} 
  
// Function to check if a palindrome pair exists 
function checkPalindromePair(vect) { 
  
  // Construct trie 
  const root = getNode(); 
    
  for (let i = 0; i < vect.length; i++) 
      insert(root, vect[i], i); 
  
  // Search for different keys 
  const result = []; 
    
  for (let i = 0; i < vect.length; i++) { 
      search(root, vect[i], i, result); 
        
      if (result.length > 0) 
          return true; 
  } 
  
  return false; 
  
} 
  
// Driver code 
  
const vect = ["geekf", "geeks", "or", "keeg", "abc", "bc"]; 
  
if (checkPalindromePair(vect)) { 
    console.log("Yes"); 
}  
else { 
    console.log("No"); 
} 
  
// This code is contributed by Amit Mangal.

Output

Yes

Time Complexity: O(nk²), Where n is the number of words in the list and k is the maximum length that is checked for palindrome.
Auxiliary Space: O(1)

Method 3:

Below given is a program which is based upon the above discussed algorithm, but instead of trie it uses hashmap datastructure for giving efficient storage and retrieval method.

Hence it reduces complexity a lot.

Implementation:

C++

// C++ program for above method  
#include <bits/stdc++.h> 
using namespace std; 
  
bool Function(vector<string> wordlist)  
{ 
  // storing word in reverse format along with their indices. 
  unordered_map<string, int> hashmap_reverse; 
  vector<pair<int, int>> ans; 
  for (int i = 0; i < wordlist.size(); i++) { 
    string word = wordlist[i]; 
    string reverse_word = string(word.rbegin(), word.rend()); 
    hashmap_reverse[reverse_word] = i; 
  } 
  
  // enumerating over all words and for each character of them 
  for (int i = 0; i < wordlist.size(); i++) { 
    string word = wordlist[i]; 
    for (int j = 0; j < word.size(); j++) { 
      // #extracting left and right of them 
      string left = word.substr(0, j + 1); 
      string right = word.substr(j + 1); 
      // checking if left exists and is palindrome and also right is present in map 
      // this is to make sure the best edge case described holds. 
      if (!left.empty() && left == string(left.rbegin(), left.rend()) && hashmap_reverse.count(right) && hashmap_reverse[right] != i) { 
        ans.emplace_back(hashmap_reverse[right], i); 
      } 
      // normal case. 
      if (right == string(right.rbegin(), right.rend()) && hashmap_reverse.count(left) && hashmap_reverse[left] != i) { 
        ans.emplace_back(i, hashmap_reverse[left]); 
      } 
    } 
  } 
  return ans.empty() ? false : true; 
} 
  
int main() { 
  vector<string> words = {"geekf", "geeks", "or","keeg", "abc", "bc"}; 
  (Function(words)==true)? cout <<  "True" : cout<< "False" ; 
  cout<< endl; 
  return 0; 
} 
  
// This code is contributed by Aman Kumar.

Java

import java.util.*; 
  
public class Main { 
    public static boolean Function(List<String> wordlist) 
    { 
        // storing word in reverse format along with their 
        // indices. 
        Map<String, Integer> hashmap_reverse 
            = new HashMap<>(); 
        List<int[]> ans = new ArrayList<>(); 
  
        for (int i = 0; i < wordlist.size(); i++) { 
            String word = wordlist.get(i); 
            String reverse_word = new StringBuilder(word) 
                                      .reverse() 
                                      .toString(); 
            hashmap_reverse.put(reverse_word, i); 
        } 
        // enumerating over all words and for each character 
        // of them 
        for (int i = 0; i < wordlist.size(); i++) { 
            String word = wordlist.get(i); 
            for (int j = 0; j < word.length(); j++) { 
                // #extracting left and right of them 
                String left = word.substring(0, j + 1); 
                String right = word.substring(j + 1); 
                // checking if left exists and is palindrome 
                // and also right is present in map this is 
                // to make sure the best edge case described 
                // holds. 
                if (!left.isEmpty() && isPalindrome(left) 
                    && hashmap_reverse.containsKey(right) 
                    && hashmap_reverse.get(right) != i) { 
                    ans.add(new int[] { 
                        hashmap_reverse.get(right), i }); 
                } 
                // normal case. 
                if (isPalindrome(right) 
                    && hashmap_reverse.containsKey(left) 
                    && hashmap_reverse.get(left) != i) { 
                    ans.add(new int[] { 
                        i, hashmap_reverse.get(left) }); 
                } 
            } 
        } 
        return !ans.isEmpty(); 
    } 
  
    public static boolean isPalindrome(String str) 
    { 
        return str.equals( 
            new StringBuilder(str).reverse().toString()); 
    } 
  
    public static void main(String[] args) 
    { 
        List<String> words = Arrays.asList( 
            "geekf", "geeks", "or", "keeg", "abc", "bc"); 
        System.out.println(Function(words)); 
    } 
}

Python3

def function(wordlist): 
  #storing word in reverse format along with their indices. 
    
    hashmap_reverse = {word[::-1]: index for index, word in enumerate(wordlist)} 
    ans = [] 
    #enumerating over all words and for each character of them 
    for index, word in enumerate(wordlist): 
        for i in range(len(word)): 
          #extracting left and right of them  
            left, right = word[:i+1], word[i+1:] 
            #checking if left exists and is palindrome and also right is present in map 
            #this is to make sure the best edge case described holds. 
              
            if not len(left) == 0 and left == left[::-1] and right in hashmap_reverse and hashmap_reverse[right] != index: 
                ans.append([hashmap_reverse[right], index]) 
                
            #normal case. 
            if right == right[::-1] and left in hashmap_reverse and hashmap_reverse[left] != index: 
                ans.append([index, hashmap_reverse[left]]) 
    if len(ans)>0: 
        return True
    return False
    
    
words = ["geekf", "geeks", "or","keeg", "abc", "bc"] 
print(function(words))

C#

using System; 
using System.Collections.Generic; 
using System.Linq; 
  
public class GFG { 
    public static bool Function(List<string> wordlist) 
    { 
        // storing word in reverse format along with their 
        // indices. 
        Dictionary<string, int> hashmap_reverse 
            = new Dictionary<string, int>(); 
        List<int[]> ans = new List<int[]>(); 
  
        for (int i = 0; i < wordlist.Count(); i++) { 
            string word = wordlist[i]; 
            string reverse_word 
                = new string(word.Reverse().ToArray()); 
            hashmap_reverse[reverse_word] = i; 
        } 
  
        // enumerating over all words and for each character 
        // of them 
        for (int i = 0; i < wordlist.Count(); i++) { 
            string word = wordlist[i]; 
  
            for (int j = 0; j < word.Length; j++) { 
                // extracting left and right of them 
                string left = word.Substring(0, j + 1); 
                string right = word.Substring(j + 1); 
  
                // checking if left exists and is palindrome 
                // and also right is present in map this is 
                // to make sure the best edge case described 
                // holds. 
                if (!string.IsNullOrEmpty(left) 
                    && isPalindrome(left) 
                    && hashmap_reverse.ContainsKey(right) 
                    && hashmap_reverse[right] != i) { 
                    ans.Add(new int[] { 
                        hashmap_reverse[right], i }); 
                } 
  
                // normal case. 
                if (isPalindrome(right) 
                    && hashmap_reverse.ContainsKey(left) 
                    && hashmap_reverse[left] != i) { 
                    ans.Add(new int[] { 
                        i, hashmap_reverse[left] }); 
                } 
            } 
        } 
        return ans.Any(); 
    } 
  
    public static bool isPalindrome(string str) 
    { 
        return str == new string(str.Reverse().ToArray()); 
    } 
  
    static public void Main(string[] args) 
    { 
        List<string> words 
            = new List<string>{ "geekf", "geeks", "or", 
                                "keeg",  "abc",   "bc" }; 
        Console.WriteLine(Function(words)); 
    } 
} 
// This code is contributed by prasad264

Javascript

// Javascript program for above method  
function checkPalindromePairs(wordlist) { 
    const hashmap_reverse = new Map(); 
    const ans = []; 
  
    // storing word in reverse format along with their indices. 
    for (let i = 0; i < wordlist.length; i++) { 
        const word = wordlist[i]; 
        const reverse_word = word.split("").reverse().join(""); 
        hashmap_reverse.set(reverse_word, i); 
    } 
  
    // enumerating over all words and for each character of them 
    for (let i = 0; i < wordlist.length; i++) { 
        const word = wordlist[i]; 
        for (let j = 0; j < word.length; j++) { 
            
            // #extracting left and right of them 
            const left = word.substring(0, j + 1); 
            const right = word.substring(j + 1); 
            
            // checking if left exists and is palindrome and also right is present in map 
            // this is to make sure the best edge case described holds. 
            if (left.length > 0 && left === left.split("").reverse().join("") && hashmap_reverse.has(right) && hashmap_reverse.get(right) !== i) { 
                ans.push([hashmap_reverse.get(right), i]); 
            } 
            
            // normal case. 
            if (right === right.split("").reverse().join("") && hashmap_reverse.has(left) && hashmap_reverse.get(left) !== i) { 
                ans.push([i, hashmap_reverse.get(left)]); 
            } 
        } 
    } 
    return ans.length > 0; 
} 
  
const words = ["geekf", "geeks", "or", "keeg", "abc", "bc"]; 
console.log(checkPalindromePairs(words) ? "True" : "False");

Output

True

Time Complexity: O(nl²) where n = length of array and l = length of longest string.
Auxiliary Space: O(n)

Sahil Chhabra (akku)

Improve

Count palindromic characteristics of a String

Minimum equal palindromic cuts with rearrangements allowed

Check Palindrome by Different Language

Easy Problems on Palindrome

Medium Problems on Palindrome

Hard Problems on Palindrome

Palindrome pair in an array of words (or strings)

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?