Hexo

2020-11-07

一、引言

212. 单词搜索 II

难度困难278

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

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

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

Trie树应用广泛， NLP 中一般会用其存储大量的字典字符以用于文本的快速分词；除此之外，典型应用场景还包括大批量文本的：词频统计、字符串查询和模糊匹配（比如关键词的模糊匹配）、字符串排序等任务；（还比如搜索引擎）。由于 Trie 大幅降低了无谓的字符串比较，因此在执行上述任务时，其效率非常的高。

二、Trie 树的简介

Trie 树中文名叫字典树、前缀树等等。这些名字暗示其与字符的处理有关，事实也确实如此，它主要用途就是将字符串（当然也可以不限于字符串）整合成树形。

这个树里面每一个方块代表一个节点，其中 ”Root” 表示根节点，不代表任何字符；紫色代表分支节点；绿色代表叶子节点。除根节点外每一个节点都只包含一个字符。从根节点到叶子节点，路径上经过的字符连接起来，构成一个词。而叶子节点内的数字代表该词在字典树中所处的链路（字典中有多少个词就有多少条链路），具有共同前缀的链路称为串。除此之外，还需特别强调 Trie 树的以下几个特点：

具有相同前缀的词必须位于同一个串内；例如“清华”、“清新”两个词都有“清”这个前缀，那么在 Trie 树上只需构建一个“清”节点，“华”和“新”节点共用一个父节点即可，如此两个词便只需三个节点便可存储，这在一定程度上减少了字典的存储空间。
Trie 树中的词只可共用前缀，不可共用词的其他部分；例如“中华”、“华人”这两个词虽然前一个词的后缀是后一个词的前缀，但在树形上必须是独立的两条链路，而不可以通过首尾交接构建这两个词，这也说明 Trie 树仅能依靠公共前缀压缩字典的存储空间，并不能共享词中的所有相同的字符；
Trie 树中任何一个完整的词，都必须是从根节点开始至叶子节点结束，这意味着对一个词进行检索也必须从根节点开始，至叶子节点才算结束。
Trie树特性：

1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3）每个节点的所有子节点包含的字符都不相同。

4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。

5）插入查找的复杂度为O(n)，n为字符串长度。

三、Trie 树的时间复杂度

在 Trie 树中搜索一个字符串，会从根节点出发，沿着某条链路向下逐字比对字符串的每个字符，直到抵达底部的叶子节点才能确认字符串为该词，这种检索方式具有以下两个优点：

基本思想（以字母树为例）：

1、插入过程
对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
2、查询过程
同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

这两个优点相结合可以最大限度地减少无谓的字符比较，使得搜索的时间复杂度理论上仅与检索词的长度有关：O(K)，其中 K 为检索词的长度。

四、Trie 树的缺点

综上可知， Trie 树主要是利用词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历，从而达到高效检索的目的。这一思想有赖于字符在词中的前后位置能够得到表达，因此其设计哲学是典型的“以信息换时间”，当然，这种优势同样是需要付出代价的：

由于结构需要记录更多的信息，因此 Trie 树的实现稍显复杂。好在这点在大多数情况下并非不可接受。
Trie 型词典不仅需要记录词，还需要记录字符之间、词之间的相关信息，因此字典构建时必须对每个词和字逐一进行处理，而这无疑会减慢词典的构建速度。对于强调实时更新的词典而言，这点可能是致命的，尤其是采用双数组实现的 Trie 树，更新词典很大概率会造成词典的全部重构，词典构建过程中还需处理各种冲突，因此重构的时间非常长

五、Trie 树的几种实现

5.1、Array Trie 树

很多文章里将这种实现称为“标准 Trie 树”，但其实它只是 Trie 众多实现中的一种而已，由于这种实现结构简单，检索效率很好，作为讲解示例很不错，因此特地改称其为“经典 Trie 树”，这里引用一下别人家的示例图[2]：

abc、d、da、dda 四个字符串构成的 Trie 树，如果是字符串会在节点的尾部进行标记。没有后续字符的 branch 分支指向NULL

如上图，这种实现的特点是：每个节点都由指针数组存储，每个节点的所有子节点都位于一个数组之中，每个数组都是完全一样的。对于英文而言，每个数组有27个指针，其中一个作为词的终结符，另外 26 个依次代表字母表中的一个字母，对应指针指向下一个状态，若没有后续字符则指向NULL。由于数组取词的复杂度为O(1)

5.2、List Trie 树

由于数组的长度是不可变，因此经典 Trie 树存在着明显的空间浪费。但是如果将每一层都换成可变数组（不同语言对这种数据结构称呼不同，比如在 Python 中为List，C# 称为 LinkedList）来存储节点（见下图[3]），每层可以根据节点的数量动态调整数组的长度，就可以避免大量的空间浪费。下图就是这种实现的图例[3]：

5.3、Hash Trie 树

可变数组取词速度太慢，用一组键值对字典类型代替可变数组：其中每个节点包含一组 Key-Value，每个 Key 对应该节点下的一个子节点字符，value 则指向相应的后一个状态。这种方式可以有效的减少空间浪费，同时由于键值对本质上就是一个哈希实现，因此理论上其查词效率也很高（理想状态下取词复杂度为O(1)