0336：回文对（★★）

力扣第 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] 由小写英文字母组成

相似问题：

• 0005：最长回文子串
• 0214：最短回文串
• 2131：连接两字母单词得到的最长回文串（1556 分）
• 2744：最大字符串配对数目（1405 分）

分析

• 单词长度较短，因此考虑直接用单词子串去搜索
• 假设 w1+w2 是回文串，分类讨论
  • w1 拆分为 a、b，b 回文，a 是 w2 的反
  • w2 拆分为 a、b，a 回文，b 是 w1 的反
• 为了方便，遍历时考虑当前单词为更长的那个即可
• 注意 w1 和 w2 长度相等，或 w1/w2 为空串的特殊情况

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        res = []
        d = {w[::-1]:i for i,w in enumerate(words)}
        for i,w in enumerate(words):
            for j in range(1,len(w)):
                a,b = w[:j],w[j:]
                if a==a[::-1] and b in d:
                    res.append([d[b],i])
                if b==b[::-1] and a in d:
                    res.append([i,d[a]])
            if w==w[::-1]:
                if w and '' in d:
                    res.append([i,d['']])
                    res.append([d[''],i])
            elif w in d:
                res.append([i,d[w]])
        return res

1460 ms