What is the main strategy for solving Palindrome Pairs efficiently?

Use array scanning combined with a hash map of reversed words, checking palindrome splits instead of brute-force pair comparisons.

How do empty strings affect palindrome pair results?

Any non-empty palindrome word can pair with an empty string in either order to form a valid palindrome pair.

Why not check every two-word combination directly?

Direct pair checks are O(n^2*k) and will exceed time limits for large arrays; hash-based splitting reduces complexity significantly.

Do we need to check both prefix and suffix splits of a word?

Yes, both prefix-palindrome/suffix-reverse and suffix-palindrome/prefix-reverse combinations can produce valid palindrome pairs.

Can this approach handle all word lengths up to 300 characters?

Yes, the algorithm efficiently handles long words using hash lookups and palindrome validation on splits without checking every pair.

#336

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

回文对

给定一个由唯一字符串构成的 0 索引数组 words 。回文对是一对整数 (i, j) ，满足以下条件： 0 ， i != j ，并且 words[i] + words[j] （两个字符串的连接）是一个回文串。返回一个数组，它包含 words 中所有满足回文对条件的字符串。你必须设…

数组哈希表字符串字典树

题目描述

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

lightbulb

解题思路

方法一：字符串哈希

字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 $0$ 。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。

取一固定值 $BASE$ ，把字符串看作是 $BASE$ 进制数，并分配一个大于 $0$ 的数值，代表每种字符。一般来说，我们分配的数值都远小于 $BASE$ 。例如，对于小写字母构成的字符串，可以令 $a=1$ , $b=2$ , ..., $z=26$ 。取一固定值 $MOD$ ，求出该 $BASE$ 进制对 $M$ 的余数，作为该字符串的 $hash$ 值。

一般来说，取 $BASE=131$ 或者 $BASE=13331$ ，此时 $hash$ 值产生的冲突概率极低。只要两个字符串 $hash$ 值相同，我们就认为两个字符串是相等的。通常 $MOD$ 取 $2^{64}$ ，C++ 里，可以直接使用 unsigned long long 类型存储这个 $hash$ 值，在计算时不处理算术溢出问题，产生溢出时相当于自动对 $2^{64}$ 取模，这样可以避免低效取模运算。

除了在极特殊构造的数据上，上述 $hash$ 算法很难产生冲突，一般情况下上述 $hash$ 算法完全可以出现在题目的标准答案中。我们还可以多取一些恰当的 $BASE$ 和 $MOD$ 的值（例如大质数），多进行几组 $hash$ 运算，当结果都相同时才认为原字符串相等，就更加难以构造出使这个 $hash$ 产生错误的数据。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	complexity is O(n _k^2) in the worst case due to splitting each word (length k) and checking palindrome validity, but hash lookups reduce unnecessary comparisons. Space complexity is O(n_ k) for storing reversed words in the hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect optimized solutions rather than brute-force O(n^2*k) pair checking.
question_mark
Watch for edge cases such as empty strings or single-character words forming palindromes.
question_mark
Clarify whether all returned pairs should be unique and correctly ordered by indices.

warning

常见陷阱

外企场景

error
Checking every two-word combination without hash optimization, leading to TLE.
error
Missing valid pairs involving empty strings or single-character palindromes.
error
Forgetting to check both prefix and suffix splits when scanning words.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return only the count of palindrome pairs instead of the index pairs.
arrow_right_alt
Find palindrome pairs in a list where words may repeat and duplicates are allowed.
arrow_right_alt
Apply the same palindrome pair logic on a stream of incoming words efficiently.

help

常见问题

外企场景

继续练习

#140 单词拆分 II #139 单词拆分 #648 单词替换