21 Mar 2025•Python•Hard

Palindrome Pairs

find all pairs of words that form palindrome when concatenated by checking all prefix/suffix splits.

for each word, try all possible splits (prefix + suffix). if prefix is palindrome, check if reverse of suffix exists in word map. if suffix is palindrome, check if reverse of prefix exists.

use hash map for O(1) word lookup. for word at index i, try splits at positions 0 to len(word). check both cases: prefix palindrome (suffix reverse in map) and suffix palindrome (prefix reverse in map).

key insight

if word1 + word2 is palindrome, either word1's prefix is palindrome (word2 reverses word1's suffix) or word1's suffix is palindrome (word2 reverses word1's prefix).

complexity

O(n * k²) time where n is words count and k is average word length. O(n) space for hash map.

Solution files

Python•palindrome-pairs/solution.py

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(word):
            return word == word[::-class="syntax-number">1]

        words_map = {word: i for i, word in enumerate(words)}
        result = []

        for i, word in enumerate(words):
            for j in range(len(word) + class="syntax-number">1):
                prefix, suffix = word[:j], word[j:]

                if is_palindrome(prefix):
                    reverse_suffix = suffix[::-class="syntax-number">1]
                    if reverse_suffix != word and reverse_suffix in words_map:
                        result.append([words_map[reverse_suffix], i])

                if j != len(word) and is_palindrome(suffix):
                    reverse_prefix = prefix[::-class="syntax-number">1]
                    if reverse_prefix != word and reverse_prefix in words_map:
                        result.append([i, words_map[reverse_prefix]])

        return result