教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解围绕 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]要让整体成为回文串只需满足下面两个条件words_right[i]本身是回文串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]此时需要满足words_left[i]本身是回文串words[j]与words_right[i]互为逆序。从上述两个推导可以提炼出统一结论words[j]可以通过拆分words[i]之后逆序得出。于是问题转化为枚举每个单词words[i]的所有拆分位置若某一段前缀或后缀自身是回文则检查剩余一段的逆序字符串是否存在于单词列表中若存在就把对应的索引对加入答案。2.2 算法步骤将整个words列表中的每个单词连同其下标索引插入字典树Trie这样任意字符串都能以 $O(L)$ 时间查询出它是否在列表中出现以及对应的索引值遍历每个单词words[i]遍历该单词的每个拆分位置j把它拆成两个部分words[i][0:j1]和words[i][j1:]若words[i][0:j1]是回文串则查找words[i][j1:]的逆序串是否在字典树中若存在且索引不是i本身则构成一对答案(words[j], words[i])的索引对若words[i][j1:]是回文串则查找words[i][0:j1]的逆序串是否在字典树中若存在且索引不是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 None3.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[:j1]): temp word[j1:][::-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[j1:]): temp word[:j1][::-1] index trie_tree.search(temp) if index ! i and index ! -1: res.append([i, index]) return res4.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[:j1]): temp word[j1:][::-1] index trie_tree.search(temp) if index ! i and index ! -1: res.append([index, i]) if temp : res.append([i, index])若前缀word[:j1]是回文则后缀word[j1:]的逆序串若能匹配到列表中的某个单词索引为index说明words[index] words[i]是回文插入[index, i]特别的当temp 即后缀为空串时说明words[i]本身就是回文此时words[i] words[index]与words[index] words[i]都是回文因此需要同时插入[i, index]。这也是处理「一个完整单词与空串」配对的核心分支。方向二后缀是回文检查前缀的逆序if self.isPalindrome(word[j1:]): temp word[:j1][::-1] index trie_tree.search(temp) if index ! i and index ! -1: res.append([i, index])若后缀word[j1:]是回文则前缀word[:j1]的逆序串若能匹配到单词列表中的某个单词说明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配合 字典树基础教程 与 字典树实现源码 一起阅读可以完整打通「数据结构原理 → 源码实现 → 实战变形」的学习链路。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0009 回文数——不转字符串的整数反转判定法AlgoNote 算法通关手册LeetCode 0009 回文数——不转字符串的整数反转判定法 导读 本篇是「算法通关手册」AlgoNote中 LeetC教程文档知识库AlgoNote 算法通关手册0125 验证回文串——对撞指针与字符串过滤实战详解AlgoNote 算法通关手册0125 验证回文串——对撞指针与字符串过滤实战详解 导读 本文讲解 LeetCode 第 0125 题「验证回文串」的完整解法教程文档知识库AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划 导读 本篇是 AlgoNote算法通关手册中 009教程文档知识库上一篇《Go语言高级编程》开源图书全览CGO、Go汇编、RPC 与分布式系统的进阶路线图下一篇CANN ops-math KLDivV2 算子完全指南aclnnKlDiv 接口、计算公式与源码级实现剖析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考