Palindrome Pairs - Leetcode Solution

Problem description:

Given a list of words, find all pairs of unique indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

Input: ["abcd","dcba","lls","s","sssll"] Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"] Output: [[0,1],[1,0]] Explanation: The palindromes are ["battab","tabbat"]

Solution:

The brute-force approach to solve this problem would be to form all possible pairs of words from the list and check whether their concatenation is a palindrome. But that approach takes O(n^2 * k) time where n is the length of the list and k is the maximum length of the words in the list.

A better approach is to use a hash table to store the indices of the words in the list as keys and their reverse form as values. For each word in the list, we can check if its prefix or suffix is a palindrome. If the prefix is a palindrome, we look for the reverse of the remaining part of the word in the hash table. Similarly, if the suffix is a palindrome, we look for the reverse of the remaining part of the word in the hash table. If we find a match in the hash table, we add the indices to the result.

Code:

Here is the Python code for the solution:

def palindrome_pairs(words: List[str]) -> List[List[int]]: # create a hash table to store the words and their indices word_dict = {word:i for i, word in enumerate(words)} result = [] for i, word in enumerate(words): # check if the reverse of the entire word is in the hash table if word[::-1] in word_dict and word_dict[word[::-1]] != i: result.append([i, word_dict[word[::-1]]]) # check if the word can be split into two parts for j in range(1, len(word)): prefix, suffix = word[:j], word[j:] # check if the prefix is a palindrome and the reverse of the remaining part of the word is in the hash table if prefix == prefix[::-1] and suffix[::-1] in word_dict: result.append([word_dict[suffix[::-1]], i]) # check if the suffix is a palindrome and the reverse of the remaining part of the word is in the hash table if suffix == suffix[::-1] and prefix[::-1] in word_dict: result.append([i, word_dict[prefix[::-1]]]) return result

Time Complexity:

The time complexity of the algorithm is O(n * k^2) where n is the number of words in the list and k is the maximum length of the words in the list. The loop over indices i and j takes O(n^2) time in the worst case. For each word, we are checking its prefix and suffix which takes O(k) time for each part. So, the total time complexity is O(n * k^2).

1