回文对

难度: Hard

给定一个由唯一字符串构成的 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] 由小写英文字母组成

Submission

运行时间: 891 ms

内存: 26.5 MB

class Solution:
     def palindromePairs(self, words: List[str]) -> List[List[int]]:
         backward, res = {}, []
         for i, word in enumerate(words):
             backward[word[::-1]] = i

         for i, word in enumerate(words):
             
             if word in backward and backward[word] != i:
                 res.append([i, backward[word]])
                 
             if word != "" and "" in backward and word == word[::-1]:
                 res.append([i, backward[""]])
                 res.append([backward[""], i])
                 
             for j in range(len(word)):
                 if word[j:] in backward and word[:j] == word[j-1::-1]:
                     res.append([backward[word[j:]], i])
                 if word[:j] in backward and word[j:] == word[:j-1:-1]:
                     res.append([i, backward[word[:j]]])
                     
         return res
solution = Solution()
assert solution.palindromePairs(words = ["abcd","dcba","lls","s","sssll"]) == [[0,1],[1,0],[3,2],[2,4]]
assert solution.palindromePairs(words = ["bat","tab","cat"]) == [[0,1],[1,0]]
assert solution.palindromePairs(words = ["a",""]) == [[0,1],[1,0]]

Explain

这个题解使用了字典 backward 来存储单词的逆序作为键，原单词的索引作为值。然后遍历每个单词，判断以下情况： 1. 如果当前单词的逆序在字典中，且不是当前单词自身，则可以组成回文对。 2. 如果当前单词是回文串，且空串在字典中，则可以组成两个回文对。 3. 将当前单词划分为左右两部分，如果左边部分的逆序在字典中，且右边部分是回文串，则可以组成回文对。 4. 将当前单词划分为左右两部分，如果右边部分的逆序在字典中，且左边部分是回文串，则可以组成回文对。最后返回所有找到的回文对。

时间复杂度: O(n*k)，其中 n 为单词数组的长度，k 为单词的平均长度。

空间复杂度: O(n^2)，其中 n 为单词数组的长度。

```python
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        backward, res = {}, []
        
        # 创建单词逆序到索引的字典
        for i, word in enumerate(words):
            backward[word[::-1]] = i
        
        # 遍历每个单词
        for i, word in enumerate(words):
            # 情况1：当前单词的逆序在字典中，且不是当前单词自身
            if word in backward and backward[word] != i:
                res.append([i, backward[word]])
            
            # 情况2：当前单词是回文串，且空串在字典中
            if word != "" and "" in backward and word == word[::-1]:
                res.append([i, backward[""]])
                res.append([backward[""], i])
            
            # 情况3和情况4：将当前单词划分为左右两部分
            for j in range(len(word)):
                # 情况3：左边部分的逆序在字典中，且右边部分是回文串
                if word[j:] in backward and word[:j] == word[j-1::-1]:
                    res.append([backward[word[j:]], i])
                # 情况4：右边部分的逆序在字典中，且左边部分是回文串
                if word[:j] in backward and word[j:] == word[:j-1:-1]:
                    res.append([i, backward[word[:j]]])
        
        return res
```

Explore

在情况2中，如果一个单词本身是回文串（例如'aba'），并且空串也存在于字典中，这个单词可以与空串形成回文对。空串作为前缀或后缀添加到回文串上仍保持整体是回文的。因此，可以形成两个回文对，一个是空串在前（例如，['', 'aba']），另一个是空串在后（例如，['aba', '']）。为了确保算法的正确性和效率，可以在创建字典时检查并添加空串，确保处理空串的逻辑清晰且不会因为频繁检查空串而降低效率。

情况3和情况4通过将单词拆分为两部分，检查其中一部分的逆序是否存在于字典中，而另一部分若是回文，则可以与逆序存在的单词形成回文对。这种方法有效地利用了字典的快速查找性能来确认单词的部分是否能形成有效的回文对。通过从第一个字符到最后一个字符逐步划分单词，这种策略确保了所有可能的拆分都被考虑到，从而找出所有可能的回文对组合。

如果单词数组中存在重复单词，字典结构需要调整以允许每个逆序单词键关联多个索引。这可以通过将字典的值从单个索引更改为索引列表来实现。在查找时，需要遍历这些索引并对每个索引执行相应的逻辑检查，确保不与当前遍历到的单词索引相同。这样可以处理重复单词的情况，并确保算法的正确性和完整性。

如果空字符串不在字典中，情况2中描述的添加空串形成回文对的情况就不会发生。在这种情况下，单独的回文串不会与空串形成对，因此不需要特别处理。只有当空串确实存在于字典中时，才能根据情况2的逻辑形成回文对。这确保了算法处理的一致性和预期行为。