前缀树 | Civilization Museum

type

status

password

date

slug

summary

简介

Trie 树也称前缀树，是一种专门处理字符串匹配的树形结构，用来解决在一组字符串集合中快速查找某个字符串的问题，Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。缺点是内存开销大。

假设有 5 个字符串，它们分别是：code，cook，five，file，fat。组织成前缀树，如下图所示：

Trie树的插入操作很简单，其实就是将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在，存在则共享该节点，不存在则创建对应的节点。

在 Trie 树中查找一个字符串的时候，比如查找字符串 code，可以将要查找的字符串分割成单个的字符 c，o，d，e，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径。

Trie树的删除操作与二叉树的删除操作有类似的地方，需要考虑删除的节点所处的位置，这里分三种情况进行分析：整个单词、删除前缀单词、删除分支单词。

情况	操作
删除`hi`整个单词	1、从根节点开始查找第一个字符 `h` 找到 `h` 子节点后；继续查找 `h` 的下一个子节点 `i` 2、`i` 是单词 `hi` 的标志位，将该标志位去掉；`i` 节点是 `hi` 的叶子节点，将其删除 3、删除后发现 `h` 节点为叶子节点，并且不是单词标志位，也将其删除，这样就完成了 `hi` 单词的删除操作
删除 `cod` 前缀单词	将 `cod` 单词整个字符串查找完后，发现d节点不是叶子节点，所以将其单词标志去掉即可
删除 `cook` 分支单词	与删除整个单词情况类似，区别点在于删除到 `cook` 的第一个 `o` 时，该节点为非叶子节点，停止删除，这样就完成 `cook` 字符串的删除操作。

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。实现词典类 WordDictionary ：

bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

实现一个 MapSum 类：

void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" 输出："the cat was rat by the bat"

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。进阶：你可以在 O(n) 的时间解决这个问题吗？

输入：nums = [3,10,5,25,2,8] 输出：28 解释：最大运算结果是 5 XOR 25 = 28.

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] 输出：["eat","oath"]

给定一组 互不相同 的单词，找出所有不同的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

输入：words = ["abcd","dcba","lls","s","sssll"] 输出：[[0,1],[1,0],[3,2],[2,4]] 解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

假设存在两个字符串和，是一个回文串，记这两个字符串的长度分别为和，我们分三种情况进行讨论：

这样，我们枚举每一个字符串，令其为和中较长的那一个，那么可以被拆分为两部分，和。