336. 回文对

题目

给定一个由唯一字符串构成的 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 <= 5000

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

words[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