336. Palindrome Pairs (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        # hash table
        h = {word: i for i, word in enumerate(words)}
        result = set()
        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                a, b = word[ : j], word[j : ]
                if b == b[ : : -1] and a[ : : -1] in h:
                    if h[a[ : : -1]] != i:
                        result.add((i, h[a[ : : -1]]))
                if a == a[ : : -1] and b[ : : -1] in h:
                    if h[b[ : : -1]] != i:
                        result.add((h[b[ : : -1]], i))
        return result
        
        # brute force TLE
        def isPal(s):
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] == s[j]:
                    i += 1
                    j -= 1
                else:
                    return False
            return True
        n = len(words)
        result = []
        for i in range(n):
            for j in range(n):
                if i != j:
                    if isPal(words[i] + words[j]):
                        result.append([i, j])
        return result