336. Palindrome Pairs

Hard

---

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 < word.length,

• i != j, and

• words[i] + words[j] (the concatenation of the two strings) is a palindrome string.

Return an array of all the palindrome pairs of words.

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output:
 [[0,1],[1,0],[3,2],[2,4]]
Explanation:
 The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"]
Output:
 [[0,1],[1,0]]
Explanation:
 The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]
Output:
 [[0,1],[1,0]]
Explanation:
 The palindromes are ["a","a"]

Constraints:

• 1 <= words.length <= 5000

• 0 <= words[i].length <= 300

• words[i] consists of lowercase English letters.

class Solution:
    def palindromePairs(self, words):
        # https://leetcode.com/problems/palindrome-pairs/discuss/2585442/Intuitive-Python3-or-HashMap-or-95-Time-and-Space-or-O(N*W2)
        d, res = dict([(w[::-1], i) for i, w in enumerate(words)]), []
        result = []
        for index, word in enumerate(words):
            if word in d and index != d[word]:
                result.append([index, d[word]])
            if word !="" and "" in d and word==word[::-1]:
                result.append([index,d[""]])
                result.append([d[""],index])
            for j in range(len(word)):
                if word[j:] in d and word[:j] == word[j-1::-1]:
                    result.append([d[word[j:]], index])
                if word[:j] in d and word[j:] == word[:j-1:-1]:
                    result.append([index, d[word[:j]]])
        return result