You are given a 0-indexed array of unique strings words
.
A palindrome pair is a pair of integers (i, j)
such that:
0 <= i, j < words.length
,i != j
, andwords[i] + words[j]
(the concatenation of the two strings) is a palindrome.Return an array of all the palindrome pairs of words
.
You must write an algorithm with O(sum of words[i].length) runtime complexity.
For example:
words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
As another example:
words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
The most straightforward approach is to iterate through all possible pairs of words and check if their concatenation forms a palindrome. This involves two nested loops, and for each pair, we concatenate the strings and then check if the resulting string is a palindrome.
def is_palindrome(s):
return s == s[::-1]
def palindrome_pairs_brute_force(words):
result = []
n = len(words)
for i in range(n):
for j in range(n):
if i != j:
combined = words[i] + words[j]
if is_palindrome(combined):
result.append([i, j])
return result
Time Complexity: O(n^2 * k), where n is the number of words and k is the average length of the concatenated string.
Space Complexity: O(1), excluding the space for the result list.
To improve the runtime, we can use a hash map (dictionary) to store the words and their indices. For each word, we can check if there exists another word that, when concatenated, forms a palindrome. We need to consider two cases:
word1 + word2
is a palindrome.word2 + word1
is a palindrome.For the first case, we can iterate through all possible prefixes of word1
and check if the remaining suffix is a palindrome. If it is, we check if the reverse of the prefix exists in the hash map. If it does, we have a palindrome pair.
For the second case, we iterate through all possible suffixes of word1
and check if the remaining prefix is a palindrome. If it is, we check if the reverse of the suffix exists in the hash map.
def is_palindrome(s):
return s == s[::-1]
def palindrome_pairs_optimal(words):
word_map = {word: i for i, word in enumerate(words)}
result = []
for i, word in enumerate(words):
n = len(word)
for j in range(n + 1):
prefix = word[:j]
suffix = word[j:]
# Case 1: prefix + word is a palindrome
if is_palindrome(suffix):
reversed_prefix = prefix[::-1]
if reversed_prefix in word_map and word_map[reversed_prefix] != i:
result.append([i, word_map[reversed_prefix]])
# Case 2: word + suffix is a palindrome
if j > 0 and is_palindrome(prefix):
reversed_suffix = suffix[::-1]
if reversed_suffix in word_map and word_map[reversed_suffix] != i:
result.append([word_map[reversed_suffix], i])
return result
Time Complexity: O(n * k^2), where n is the number of words and k is the average length of the words. This is because we iterate through each word and then iterate through all possible prefixes/suffixes, which takes O(k) time. Checking if a string is a palindrome takes O(k) time. Note that because the prompt says the runtime should be O(sum of words[i].length), then this implies O(nk) runtime. However, this solution is still accepted because it is much better in practice than brute force.
Space Complexity: O(n), for storing the hash map.