Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

Trie 的应用场景: 一次建树，多次查询

前缀树的3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

前缀树查询和哈希查询的比较（示相对情况而定）：
通常字典树的查询时间复杂度是O(logL)，L是字符串的长度。

适用场景：

  1. 字符串的快速检索
  2. 字符串排序
  3. 最长公共前缀
  4. 自动匹配前缀显示后缀

208. 实现 Trie (前缀树)

三个单词 “sea”,”sells”,”she” 的 Trie

image.png
image.png

  1. class TrieNode {
  2.     children;
  3.     isEnd;
  4.     constructor() {
  5.         this.children = new Array(26);
  6.         this.isEnd = false;
  7.     }
  8. }
  10. class Trie {
  11.     root;
  12.     constructor() {
  13.         this.root = new TrieNode();
  14.     }
  16.     insert(word: string): void {
  17.         let head = this.root;
  18.         for (let char of word) {
  19.             let index = char.charCodeAt(0) - 97;
  20.             if (!head.children[index]) {
  21.                 head.children[index] = new TrieNode();
  22.             }
  23.             head = head.children[index];
  24.         }
  25.         head.isEnd = true;
  26.     }
  28.     search(word: string): boolean {
  29.         let head = this.searchPrefix(word);
  30.         return head != null && head.isEnd;
  31.     }
  33.     startsWith(prefix: string): boolean {
  34.         return this.searchPrefix(prefix) != null;
  35.     }
  37.     private searchPrefix(prefix: string) {
  38.         let head = this.root;
  39.         for (let char of prefix) {
  40.             let index = char.charCodeAt(0) - 97;
  41.             if (!head.children[index]) return null;
  42.             head = head.children[index];
  43.         }
  44.         return head;
  45.     }
  46. }

720. 词典中最长的单词

692. 前K个高频单词

练习：

面试题 17.17. 多次搜索

LC练习：

677. 键值映射

返回所有以该前缀 prefix 开头的键 key 的值的总和

676. 实现一个魔法字典

判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配

421. 数组中两个数的最大异或值