题目 #
给定一个由唯一字符串构成的 0 索引 数组 words 。
回文对 是一对整数 (i, j) ，满足以下条件：
-
0 <= i, j < words.length， -
i != j，并且 -
words[i] + words[j]（两个字符串的连接）是一个。回文串
返回一个数组，它包含 words 中所有满足 回文对 条件的字符串。
你必须设计一个时间复杂度为 O(sum of words[i].length) 的算法。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为["dcbaabcd","abcddcba","slls","llssssll"]示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为["battab","tabbat"]示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]提示：
1 <= words.length <= 50000 <= words[i].length <= 300words[i]由小写英文字母组成
解法 #
如果 word_i 和 word_j 能够拼成一个回文串，那么我们考虑 word_i 和 word_j_inverse, 二者必然其中一个是另一个的前缀，并且较长的那个剩下的部分，本身是一个回文串。
比如 abc + deedcba 是一个回文串，那么 abc 是 abcdeed (deedcba 的逆串) 的前缀，且剩下的部分 deed 也是一个回文串。
我们将所有的逆串存储到字典树中，由于最终答案要输出的是下标列表，因此我们在字典树的终止节点中存放的是愿数组中的下标位置。
之后我们遍历 words, 同时试图在字典树中找到符合条件的 word_j_inverse, 存在如下两种情况：
-
len(word_i) > len(word_j_inverse)我们检测 word_i 的剩余部分是不是回文串，是的话，则 i,j 可构成一对
-
len(word_i) <= len(word_j_inverse)我们找到所有存储于此路径下的 word_j_inverse, 检查剩余部分是否为回文串，是的话, 则对应的 i,j 可构成一对
代码 #
class Trie:
def __init__(self):
self.root = {'idx': -1}
def add(self, word, idx):
node = self.root
for c in word:
if c not in node:
node[c] = {'idx': -1}
node = node[c]
node['idx'] = idx
def wordTails(self, node, res = []):
if node['idx'] != -1:
res.append(node['idx'])
for x in node.keys():
if x != 'idx':
self.wordTails(node[x], res)
return res
class Solution:
def __init__(self):
self.trie = Trie()
self.drows = []
def isPalindrome(self, s):
n = len(s)
for i in range(n//2):
if s[i] != s[n-1-i]:
return False
return True
def doSearch(self, word, i, index, node, res = []):
if i == len(word):
idxes = self.trie.wordTails(node, [])
for idx in idxes:
if self.isPalindrome(self.drows[idx][i:]):
if index != idx:
res.append([index, idx])
else:
if node['idx'] != -1 and self.isPalindrome(word[i:]):
if index != node['idx']:
res.append([index, node['idx']])
c = word[i]
if c in node:
self.doSearch(word, i+1, index, node[c], res)
return res
def palindromePairs(self, words: List[str]) -> List[List[int]]:
self.trie = Trie()
self.drows = []
ans = []
for i in range(len(words)):
word = words[i]
drow = word[::-1]
self.drows.append(drow)
self.trie.add(drow, i)
for i in range(len(words)):
word = words[i]
ans += self.doSearch(word, 0, i, self.trie.root, [])
return ans