Palindrome Pairs — Trie + Palindrome Check

Problem

Find all pairs (i,j) such that words[i] + words[j] is a palindrome.

Approach — HashMap (simpler than Trie)

For each word w at index i, check:

If reverse of w is in dict → full palindrome
For each split w[:k] where w[k:] is palindrome, if reverse(w[:k]) in dict
For each split w[k:] where w[:k] is palindrome, if reverse(w[k:]) in dict

Time: O(n * L²) | Space: O(n * L)

Solutions

Python — HashMap

class Solution:
    def palindromePairs(self, words: list[str]) -> list[list[int]]:
        word_map={w:i for i,w in enumerate(words)}
        def is_pal(s): return s==s[::-1]
        res=[]
        for i,w in enumerate(words):
            for k in range(len(w)+1):
                # prefix palindrome: w[k:] + reverse of w[:k]
                if is_pal(w[k:]):
                    rev=w[:k][::-1]
                    if rev in word_map and word_map[rev]!=i:
                        res.append([i,word_map[rev]])
                # suffix palindrome: reverse of w[k:] + w[:k]
                if k>0 and is_pal(w[:k]):
                    rev=w[k:][::-1]
                    if rev in word_map and word_map[rev]!=i:
                        res.append([word_map[rev],i])
        return res

Complexity

Time: O(n * L²) | Space: O(n * L)