1
class Solution:
2
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
3
        m = {}
4
        for i, word in enumerate(words):
5
            m[word] = i
6

7
        result = set()
8
        for i, word in enumerate(words):
9
            n, rev_word = len(word), word[::-1]
10
            prefix, suffix = word, rev_word
11

12
            for j in range(n + 1):
13
                if prefix == suffix:
14
                    key = rev_word[:j]
15
                    if key in m and m[key] != i:
16
                        result.add((m[key], i))
17

18
                if j == n:
19
                    break
20

21
                prefix = prefix[:-1]
22
                suffix = suffix[1:]
23

24
            # print('pre', i, result)
25

26
            prefix, suffix = "", ""
27
            for j in range(n + 1):
28
                if prefix == suffix:
29
                    if prefix == suffix:
30
                        key = rev_word[j:]
31
                        if key in m and m[key] != i:
32
                            result.add((i, m[key]))
33

34
                if j == n:
35
                    break
36

37
                prefix = word[n - j - 1] + prefix
38
                suffix = suffix + rev_word[j]
39

40
            # print('post', i, result)
41

42
        return list(result)