leetcode-336 Palindrome Pairs

[336] Palindrome Pairs

Key Concept: Trie or HashMap with Reverse Lookup - For each word, check if its reverse (or partial reverse) exists in the dictionary and forms a palindrome when concatenated.

# Given a list of unique strings words, return all pairs of distinct indices
# such that the concatenation of the two words is a palindrome.

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        word_dict = {word: i for i, word in enumerate(words)}
        result = []

        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                prefix, suffix = word[:j], word[j:]

                # Check if prefix is palindrome and reversed suffix exists
                if prefix == prefix[::-1]:
                    reversed_suffix = suffix[::-1]
                    if reversed_suffix in word_dict and word_dict[reversed_suffix] != i:
                        result.append([word_dict[reversed_suffix], i])

                # Check if suffix is palindrome and reversed prefix exists
                if j != len(word) and suffix == suffix[::-1]:
                    reversed_prefix = prefix[::-1]
                    if reversed_prefix in word_dict and word_dict[reversed_prefix] != i:
                        result.append([i, word_dict[reversed_prefix]])

        return result

# Time: O(n * k^2), Space: O(n)
# AirBnB: Tests string manipulation and hash table usage