A palindrome is a word, phrase, or number which reads the same as backward as forward. For example, "noon" or "madam", etc. Finding such palindromic pairs from the given list of unique words is one of the most commonly asked interview questions. This question has already been asked during the technical interview of Microsoft as it helps the interviewer to test the problem-solving ability and concept understanding of the candidate. Because data structure and algorithm are the main focus of any interview, this problem involves the application of the same and therefore, today we will understand the palindromic pairs problem with its different solution approaches in detail. Let's get started!
What is the Palindrome Pairs Problem?
"You are given a list of n unique words. Find the pair(k,l) of distinct indices in the given list such that concatenation of the word[k] + word[l] is a palindrome."
Confusing right?. Take a look at the below example for a simple understanding of the problem.
Consider you are given the list as [‘app,’ ‘root,’ ‘ppa’].
If you concatenate the word[0] with [2], it will form a palindrome. Similarly, if you concatenate word[2] with word[0], it will also give you a palindromic sequence.
Coding the solution to the above problem is tricky if you don’t know the correct approach. Therefore, we have provided two simple approaches to understand the roadmap for finding the palindromic pairs for a given list of words.
Solutions of Palindromic Pairs Problem
You can solve palindromic pairs problem using the below-given methods:
Method 1: Brute Force Approach
After understanding the problem, the first solution that comes to your mind is to traverse through the list and concatenate each word with another word to check whether the string is palindrome or not. If you follow this approach, the output will be correct, and you will find the palindromic pairs.
If you consider the brute force approach to find the solution to the problem, traversing through the entire list of words and concatenating it over and over will eventually increase the time complexity of the solution. Hence, it won’t count as optimal.
Method 2: Optimal Approach
To find the optimal solution, instead of pairing each word from the list, you can figure out what possible words would pair with each other and specifically check the palindromic condition for those words.
You have to store each word in a map data structure where the key will be the given words, and the value will be the index of the words in the list. You can consider all possible word matches with the current word and iterate through the list using this.
Also, you have to define a function to check whether the word is a palindrome. Therefore, rather than passing the whole substring of the word, you can specify a range of indexes to check the palindromic condition and not constantly build new strings.
As you iterate through words, each word will possibly match with another in one of the following ways:
1) A null string will match on any side with any palindrome word. This condition is easy to check because if you find the blank string, you can iterate through the entire list of words with extra time searching for finding the palindromes. The only thing to remember is not to match the blank string with itself. For example, "" will match with "xyz" and vice versa.
2) A partial word string will match with its reverse version on the opposite side of the left portion of the word is a palindrome. For example, if the string is "xyzuuu", it will match with "zyx" because the left portion of the first string, i.e. "xyz", matches with "zyx" and "uuu" is a palindrome itself. Since we eventually iterate to match a full word, we must only add one pair this time. It is because we will be able to add the second ordering of the same pair when we get the second word.
3) A full word string will match on either side with its reverse version. For example, if the word is "xyz", it will match with "zyx" and vice versa. To check this condition, we will first reverse the current string to its backward and match it with the similar string in its frontwards form. This condition is most difficult to check because we have to iterate through the indexes of the words themselves and match both sides of the words for palindrome.
If we find the palindrome pairs in any of the above conditions, we will push that pair to our answer array and return the array as output.
Palindrome Pairs Code in 3 Different Programming Languages
1) Python Code
Below is the python code for the optimal solution to find the palindrome pairs from the given list of words.
class TrieNode : def __init__ ( self ) : self.children = {} self.isEnd = False self.index = -1 class Trie : def __init__ ( self ) : self.root = TrieNode () def insert ( self , word , index ) : node = self.root for char in word : if char not in node.children : node.children [ char ] = TrieNode () node = node.children [ char ] node.isEnd = True node.index = index def search ( self , word ) : node = self.root for char in word : if char not in node.children : return (False , -1) node = node.children [ char ] return (node.isEnd , node.index) class Solution : def pairPalindrome ( self , words ) : def is_palindrome ( check ) : return check == check [ : :-1 ] trie = Trie () for i , word in enumerate ( words ) : trie.insert ( word , i ) valid_pals = [ ] for i , word in enumerate ( words ) : m = len ( word ) for k in range ( m + 1 ) : prefix = word [ :k ] suffix = word [ k : ] if is_palindrome ( prefix ) : search , index = trie.search ( suffix [ : :-1 ] ) if search and index != i : valid_pals.append ( [ index , i ] ) if k != m and is_palindrome ( suffix ) : search , index = trie.search ( prefix [ : :-1 ] ) if search and index != i : valid_pals.append ( [ i , index ] ) return valid_pals if __name__ == '__main__': words = ["pa","a","tot","","anagram","cpp","p"] print(Solution().pairPalindrome(words))
2) Java Code
Below is the java code to find the palindrome pairs from the given list of words:
public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> al=new ArrayList<List<Integer>>(); for(int i=0;i<words.length-1;i++) { for(int j=i+1;j<words.length;j++) { String k=words[i]+words[j]; String t=words[j]+words[i]; if(ispalin(k)) { ArrayList<Integer> l=new ArrayList<Integer>(); l.add(i); l.add(j); al.add(l); } if(ispalin(t)) { ArrayList<Integer> l=new ArrayList<Integer>(); l.add(j); l.add(i); al.add(l); } } } return al; } boolean ispalin(String s) { int i=0; int j=s.length()-1; while(i<j) { if(s.charAt(i)!=s.charAt(j)) return false; i++; j--; } return true; }
3) C++ Code
Below is the C++ code to find the palindrome pairs from the given list of words:
class TrieNode : def __init__ ( self ) : self.children = {} self.isEnd = False self.index = -1 class Trie : def __init__ ( self ) : self.root = TrieNode () def insert ( self , word , index ) : node = self.root for char in word : if char not in node.children : node.children [ char ] = TrieNode () node = node.children [ char ] node.isEnd = True node.index = index def search ( self , word ) : node = self.root for char in word : if char not in node.children : return (False , -1) node = node.children [ char ] return (node.isEnd , node.index) class Solution : def pairPalindrome ( self , words ) : def is_palindrome ( check ) : return check == check [ : :-1 ] trie = Trie () for i , word in enumerate ( words ) : trie.insert ( word , i ) valid_pals = [ ] for i , word in enumerate ( words ) : m = len ( word ) for k in range ( m + 1 ) : prefix = word [ :k ] suffix = word [ k : ] if is_palindrome ( prefix ) : search , index = trie.search ( suffix [ : :-1 ] ) if search and index != i : valid_pals.append ( [ index , i ] ) if k != m and is_palindrome ( suffix ) : search , index = trie.search ( prefix [ : :-1 ] ) if search and index != i : valid_pals.append ( [ i , index ] ) return valid_pals if __name__ == '__main__': words = ["pa","a","tot","","anagram","cpp","p"] print(Solution().pairPalindrome(words))
Time Complexity
The time complexity of the optimal solution will be O(n*m^2), where n is the length of words and m is the average length of the words. Similarly, the space complexity of the problem will be O(n) as you make use of map data structure for storing the words.
Conclusion
Even though the palindrome pairs problem seems easy to understand, it is pretty tricky to solve it if you are unaware of the correct approach. Therefore, in this article, we have presented an optimal approach to solving this problem and coding solutions in Python, Java, and C++. Still, if you face any difficulty finding the output of the problem, get in touch with our live coding help tutors and immediately solve your doubts.
