企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇题解围绕 docs/solutions/0300-0399/palindrome-pairs.md 展开，讲解 LeetCode 0336「回文对」的题目含义、拆分思想与基于字典树（Trie）的高效实现。读完本文，你将掌握如何把「判断两字符串拼接是否为回文」的问题，转化为「前缀回文 + 逆序查找」的组合问题，并能在 Python 中手写带索引信息的字典树完成求解。本文同时结合 AlgoNote 仓库中的字典树基础教程与实现源码进行纵深印证。

一、题目概述

题目链接：0336. 回文对

• 标签：字典树、数组、哈希表、字符串
• 难度：困难
• 题目大意：给定一组互不相同的单词列表words，要求找出所有不同的索引对(i, j)，使得列表中的两个单词words[i] + words[j]拼接后能构成回文串。

直观上看，这是一个「两两配对」问题：words列表长度记为n，朴素做法是枚举所有(i, j)组合并逐一验证拼接结果，单次回文判断需要遍历整个拼接串，整体代价为 $O(n^2 \cdot L)$（L为单词平均长度）。当n较大时，这种暴力枚举无法通过。本篇文章给出的字典树解法，正是针对「逆序字符串是否存在于单词列表」这一高频查询进行加速的核心思路。

二、解题思路：把拼接回文拆成「回文段 + 逆序段」

2.1 核心推导

设字符串words[i] + words[j]能构成回文串。把words[i]拆分成两部分：

words[i] = words_left[i] + words_right[i] words[i] + words[j] = words_left[i] + words_right[i] + words[j]

要让整体成为回文串，只需满足下面两个条件：

1. words_right[i]本身是回文串；
2. words_left[i]与words[j]互为逆序（即words[j]恰好等于words_left[i]反转后的结果）。

同理，考虑words[j] + words[i]能构成回文串的情形，把words[i]拆成words_left[i] + words_right[i]：

words[j] + words[i] = words[j] + words_left[i] + words_right[i]

此时需要满足：

1. words_left[i]本身是回文串；
2. words[j]与words_right[i]互为逆序。

从上述两个推导可以提炼出统一结论：words[j]可以通过拆分words[i]之后逆序得出。于是问题转化为：枚举每个单词words[i]的所有拆分位置，若某一段（前缀或后缀）自身是回文，则检查剩余一段的逆序字符串是否存在于单词列表中；若存在，就把对应的索引对加入答案。

2.2 算法步骤

1. 将整个words列表中的每个单词连同其下标索引插入字典树（Trie），这样任意字符串都能以 $O(L)$ 时间查询出它是否在列表中出现，以及对应的索引值；
2. 遍历每个单词words[i]；
3. 遍历该单词的每个拆分位置j，把它拆成两个部分words[i][0:j+1]和words[i][j+1:]；
4. 若words[i][0:j+1]是回文串，则查找words[i][j+1:]的逆序串是否在字典树中；若存在且索引不是i本身，则构成一对答案(words[j], words[i])的索引对；
5. 若words[i][j+1:]是回文串，则查找words[i][0:j+1]的逆序串是否在字典树中；若存在且索引不是i本身，则构成一对答案(words[i], words[j])的索引对。

这里「判断某段字符串是否是回文」以及「查找逆序字符串对应的索引」分别由isPalindrome函数与字典树的search方法完成。

三、前置知识：字典树（Trie）及其索引扩展

3.1 字典树是什么

字典树（Trie），又称前缀树，是一种高效存储和查找字符串集合的树形结构：根节点不存储字符，其余每个节点存储一个字符，从根节点到某个节点的路径恰好组成一个字符串；具有相同前缀的单词共用同一条路径。其基本性质包括：

• 根节点不存字符，其他每个节点只存一个字符；
• 从根到某节点的路径组成该节点对应的字符串；
• 每个节点的所有子节点字符都不相同。

AlgoNote 仓库在 字典树基础教程 中对 Trie 的结构、插入、查找与复杂度做了完整讲解，并给出了可运行的实现代码。仓库中的 字典树实现源码 以Node（字符节点）与Trie（字典树）两个类组织：

class Node: # 字符节点 def __init__(self): # 初始化字符节点 self.children = dict() # 初始化子节点 self.isEnd = False # isEnd 用于标记单词结束 class Trie: # 字典树 def __init__(self): self.root = Node() # 初始化根节点（根节点不保存字符） def insert(self, word: str) -> None: cur = self.root for ch in word: if ch not in cur.children: cur.children[ch] = Node() cur = cur.children[ch] cur.isEnd = True def search(self, word: str) -> bool: cur = self.root for ch in word: if ch not in cur.children: return False cur = cur.children[ch] return cur is not None and cur.isEnd def startsWith(self, prefix: str) -> bool: cur = self.root for ch in prefix: if ch not in cur.children: return False cur = cur.children[ch] return cur is not None

3.2 回文对题解中对字典树的扩展

上面这份实现中，search只回答「单词是否存在」。而在 0336 题中，我们不仅需要知道逆序字符串是否出现在列表中，还需要拿到它对应的单词下标。因此题解代码对节点做了两处扩展：

• 每个节点增加self.index = -1，用于在单词结束节点记录该单词在原列表中的下标；
• insert方法在遍历完整个单词后，除了设置isEnd = True，还把index一并写入；
• search方法在确认目标字符串是完整单词时，直接返回其index，否则返回-1。

这正是「把数据结构稍加改造以承载业务信息」的典型做法：字典树不仅能做前缀检索，还可以在每个终止节点上挂载附加数据（计数、索引、映射值等）。仓库中 0208. 实现 Trie (前缀树) 给出了字典树类三件套（insert/search/startsWith）的标准实现，可以作为理解本题 Trie 变体的参照。

四、完整题解代码与逐段解读

以下是 docs/solutions/0300-0399/palindrome-pairs.md 给出的完整实现：

class Trie: def __init__(self): """ Initialize your data structure here. """ self.children = dict() self.isEnd = False self.index = -1 def insert(self, word: str, index: int) -> None: """ Inserts a word into the trie. """ cur = self for ch in word: if ch not in cur.children: cur.children[ch] = Trie() cur = cur.children[ch] cur.isEnd = True cur.index = index def search(self, word: str) -> int: """ Returns if the word is in the trie. """ cur = self for ch in word: if ch not in cur.children: return -1 cur = cur.children[ch] if cur is not None and cur.isEnd: return cur.index return -1 class Solution: def isPalindrome(self, word: str) -> bool: left, right = 0, len(word) - 1 while left < right: if word[left] != word[right]: return False left += 1 right -= 1 return True def palindromePairs(self, words: List[str]) -> List[List[int]]: trie_tree = Trie() size = len(words) for i in range(size): word = words[i] trie_tree.insert(word, i) res = [] for i in range(size): word = words[i] for j in range(len(word)): if self.isPalindrome(word[:j+1]): temp = word[j+1:][::-1] index = trie_tree.search(temp) if index != i and index != -1: res.append([index, i]) if temp == "": res.append([i, index]) if self.isPalindrome(word[j+1:]): temp = word[:j+1][::-1] index = trie_tree.search(temp) if index != i and index != -1: res.append([i, index]) return res

4.1 回文判断函数

def isPalindrome(self, word: str) -> bool: left, right = 0, len(word) - 1 while left < right: if word[left] != word[right]: return False left += 1 right -= 1 return True

双指针从字符串两端向中间收拢，一旦发现对应位置字符不等立即返回False；全部字符对称则返回True。空字符串（长度为 0）天然满足回文条件，这一点在下面的空串特判中会用到。

4.2 构建带索引的字典树

trie_tree = Trie() size = len(words) for i in range(size): word = words[i] trie_tree.insert(word, i)

把words中每个单词连同其下标插入字典树。由于题目保证单词互不相同，每个终止节点上的index是唯一的，不会出现覆盖歧义。

4.3 枚举拆分位置并配对

主循环分两个方向处理，对应 2.1 节的两条推导：

方向一：前缀是回文，检查后缀的逆序

if self.isPalindrome(word[:j+1]): temp = word[j+1:][::-1] index = trie_tree.search(temp) if index != i and index != -1: res.append([index, i]) if temp == "": res.append([i, index])

• 若前缀word[:j+1]是回文，则后缀word[j+1:]的逆序串若能匹配到列表中的某个单词（索引为index），说明words[index] + words[i]是回文，插入[index, i]；
• 特别的，当temp == ""（即后缀为空串）时，说明words[i]本身就是回文，此时words[i] + words[index]与words[index] + words[i]都是回文，因此需要同时插入[i, index]。这也是处理「一个完整单词与空串」配对的核心分支。

方向二：后缀是回文，检查前缀的逆序

if self.isPalindrome(word[j+1:]): temp = word[:j+1][::-1] index = trie_tree.search(temp) if index != i and index != -1: res.append([i, index])

• 若后缀word[j+1:]是回文，则前缀word[:j+1]的逆序串若能匹配到单词列表中的某个单词，说明words[i] + words[index]是回文，插入[i, index]。

两处均通过index != i排除「自己与自己拼接」的非法情况，并通过index != -1确认逆序串确实存在于字典树中。

4.4 空串与自身回文的边界情况

当拆分位置j使得某一段为空时，另一段就是完整单词本身。若该单词自身是回文串，那么它与空串拼接（无论是空串在前还是在后）依然构成回文。此时temp == ""分支会把[i, index]与[index, i]成对补全，避免遗漏这种双向答案。

五、复杂度分析

从代码结构可以推导出以下复杂度结论：

• 建树阶段：遍历words中全部n个单词并逐个插入，每个单词长度为 $L$，插入操作与单词长度成正比，总时间复杂度为 $O(\sum_{i} L_i)$，即所有单词长度之和；
• 查询阶段：每个单词words[i]被拆分为 $L_i$ 个位置，每个位置最多执行两次isPalindrome（$O(L_i)$）与两次字典树查找（$O(L_i)$），因此单个单词的代价约为 $O(L_i^2)$，整体查询时间复杂度约为 $O(\sum_{i} L_i^2)$；
• 空间复杂度：字典树节点总数为所有单词的字符总数级别，若用哈希表存储子节点（本题实现即如此），空间复杂度约为 $O(\sum_{i} L_i)$。

需要说明的是，以上推导基于本仓库题解代码的实现结构；LeetCode 官方约束下，该解法相对朴素的 $O(n^2 \cdot L)$ 全枚举方案在单词数量大、长度短的测试数据下优势明显，而最坏情形（单词长度普遍偏长）时，拆分的平方开销仍不可忽视，这是该思路固有的取舍。

六、延伸与关联：Trie 在字符串配对类题目中的更多应用

回文对并不是字典树在本仓库中的唯一用武之地。类似「用一个数据结构加速字符串之间的匹配」的题目还有：

• 0425. 单词方块：同样是困难题，同样是「字典树 + 搜索」的配合。它利用字典树的startsWith前缀查询能力，在回溯过程中根据已选单词逐列推出下一行单词的前缀，再在 Trie 中检索所有匹配该前缀的候选词；
• 0208. 实现 Trie (前缀树)：字典树三件套的模板题，insert/search/startsWith是理解本题目Trie变体的基础；
• 0005. 最长回文子串：回文判断本身是本题的前置技能，该题解讲解了回文串的经典判定与最长回文子串的求解思路。

如需按主题检索更多题目，可查看仓库的 字典树题目列表（位于「字典树题目」小节）以及 题解总目录，其中 0336 回文对被收录在字典树类困难题序列中。

七、小结

LeetCode 0336「回文对」的难点在于：两两配对的数量级太大，无法朴素枚举。本题解给出的字典树方案抓住了问题的本质——拼接回文的充要条件可以拆解为「一段自身回文 + 另一段的逆序存在于单词表」，从而把「成对匹配」转化为「逆序字符串的成员查询」。而字典树恰好能以线性于字符串长度的代价完成这种查询，配合在每个终止节点上存储单词下标，一次search即可同时拿到「是否存在」与「是哪个下标」两个关键信息。

最终把完整的 Python 解法沉淀在 docs/solutions/0300-0399/palindrome-pairs.md，配合 字典树基础教程 与 字典树实现源码 一起阅读，可以完整打通「数据结构原理 → 源码实现 → 实战变形」的学习链路。

• 教程
• 文档
• 知识库