給一串文字串列，問說哪些兩個組合可以變成 Palindrome 回文。
這兩兩組合會有前後順序的差異，如果用最直觀的暴力破解法，跑遍每個組合，時間複雜度會是 O(n*(n-1))，O(n**2)。
列在 trie 的範圍內，這提示我們要使用 trie 去建立搜尋樹。要如何建立能找出回文的 trie ？
想一下回文的特性，如果是回文，頭跟尾會是相等的，頭跟尾往中間移動的字也會兩兩相等。
abcd|dcba, s|lls, lls|sssll => abcd|abcd., s|s.ll, lls|lls.ss
如果用顛倒的字詞建立 trie ，在搜尋過程中就可以前尾兩兩對消，如果過程找到字詞，只要確保「 . 」之後找到底也是回文的就可以。
aa|a => a.a|a.
萬一輸入的字詞找完之前，就先找到比較短的顛倒字詞，也代表後面不會再有字可以添加，先後對消後，只需要針對搜尋詞還沒找部分做回文判斷即可。
class Solution:
def palindromePairs(self, words):
result = []
if words:
trie = {} #反向
# create Trie
n = len(words)
for i in range(n):
cur = trie
for char in words[i][::-1]:
if char not in cur:
cur[char] = {}
cur = cur[char]
cur['end'] = i
# 檢查對稱
def isSymmetry(word):
n = len(word)
for i in range(n//2):
if word[i] != word[n-1-i]: return False
return True
#
def search1(idx, temp, cur):
"""搜尋當前字詞"""
if temp:
# 如果過程中找到字詞，檢查當前的剩餘部分是否回文
if 'end' in cur and isSymmetry(temp) and idx != cur['end']:
result.append([idx, cur['end']])
if temp[0] in cur:
search1(idx, temp[1:], cur[temp[0]])
else:
search2(idx, "", cur)
def search2(idx, temp, cur):
"""搜尋剩餘部分是否回文"""
for key in cur:
if key == "end":
if isSymmetry(temp) and idx != cur['end']:
result.append([idx, cur['end']])
else:
search2(idx, temp+key, cur[key])
#
for i in range(n):
search1(i, words[i], trie)
return result
在效率上還是太慢，我搜尋是用更廣的對稱，涵蓋更多的可能性。看了一下前段班的寫法，去找更好的思路。
如果在搜尋上，是把字文拆出「可能」組合成回文的部分搜尋，就能提升效率，但我那時有思考到這種方式，但沒有寫想到要怎麼寫，因為我trie總是用成一層層，所以被侷限了。
字詞可以整個直接當成字典的鍵使用，該鍵的值就是位置。
像是 abcd，如果要拆成回文形式，就得找出左右之分。
abcd 前組後：
abcd | “” => “”是回文 => dcba(前面部分反序) => [0,1] #前組後
abc | d => d是回文 => cba => not found
ab | cd => cd不是回文 => X
a | bcd => cbd不是回文 => X
“” | abcd => abcd不是回文 => X
換個字詞
s 前組後：
s | “” => “”是回文 => s => [3,3] => 不合規則
“” | s => s是回文 => “” => not found
lls 前組後：
lls | “” => “”是回文 => sll => not found
ll | s =>> s是回文 => ll => not found
l | ls => ls不是回文 => X
“” | lls => lls不是回文 => X
這樣的搜尋只有「前組後」，沒有考慮到「後組前」，要考慮 後組前 只要把字詞反序做搜尋。
lls 後組前：
sll(字詞反序) | “” => “”是回文 => lls => [2,2] => 不合規則
sl | l => l是回文 => ls => not found
s | ll => ll是回文 => s => [3,2] #後組前
“” | sll => sll不是回文 => X
這樣搜尋速度快不少，不過會有答案會重複，所以要想辦法去掉。
class Solution:
def palindromePairs(self, words):
table = dict(map(reversed, enumerate(words)))
res = set()
for i, word in enumerate(words):
for k in range(len(word)+1):
a = word[:k]
b = word[k:]
if a == a[::-1] and table.get(b[::-1], i) not in [-1, i]:
res.add((table.get(b[::-1], -1), i))
if b == b[::-1] and table.get(a[::-1], i) not in [-1, i]:
res.add((i, table.get(a[::-1], -1)))
return list(res)