Palindrome Pairs

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in companies
FacebookAmazonCIS - Cyber Infrastructure

Problem statement

You are given a list of ‘N’ words ‘WORDS’. Your task is to return all pairs of the distinct indices (i, j) in ‘WORDS’, such that the concatenation of WORDS[i] and WORDS[j] is a palindrome.

For Example:

You are given ‘WORDS’ = [“cat”, “mat”, “tac”]. Then the answer will be [(0, 2), (2, 0)}, because “cat” + “tac” = “cattac” which is a palindrome and “tac” + “cat” = “taccat” which is also a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer ‘N’, representing the number of words in ‘WORDS’.

The next ‘N’ lines contain a String, representing a word of ‘WORDS’’.
Output Format: 
For each test case, print all pairs of the distinct indices (i, j) in ‘WORDS’, such that the concatenation of WORDS[i] and WORDS[j] is a palindrome.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
2 <= N <= 1000
0 <= WORDS[i].LENGTH <= 100
WORDS[i] consists of lowercase English letters

Time Limit: 1 sec
Sample Input 1:
2
3
cat
mat
tac
3
ab  
ba
bb
Sample Output 1:
0 2 
2 0
0 1
1 0
Explanation of Sample Input 1:
For the first test case, the answer will be [(0, 2), (2, 0)], because “cat” + “tac” = “cattac” which is a palindrome, and “tac” + “cat” = “taccat” which is also a palindrome.

For the second test case, the answer will be [(0, 1), (1, 0)], because “ab” + “ba” = “abba” which is a palindrome, and “ba” + “ab” = “baab” which is also a palindrome.
Sample Input 2:
2
2
abc 
cba
3
wow
bow 
wob
Sample Output 2:
0 1
1 0
1 2
2 1
Hint

Check every pair of words.

Approaches (3)
Brute Force

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’.
Time Complexity

O((N ^ 2) * K), where 'N' is the length of 'WORDS' and 'K' is the length of the longest word in 'WORDS'.
 

We are iterating over each pair, and appending, reversing, and comparing each pair takes O(K) time. Hence, the total time complexity is O((N ^ 2) * K).

Space Complexity

O((N ^ 2) * K), where 'N' is the length of 'WORDS' and 'K' is the length of the longest word in 'WORDS'.
 

We may have to store ‘N’ ^ 2 words of length 2 * ‘K’. Hence, the total space complexity is O((N ^ 2) + K).

Code Solution
(100% EXP penalty)
Palindrome Pairs
Full screen
Console