Trie 树，也叫字典树，它是一个多叉树。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。其本质就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

Trie 可视化：https://www.cs.usfca.edu/~galles/visualization/Trie.html

Trie 的基础知识可以查看 算法与数据结构之美——35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？

  1. class Node {
  2.   isWord: boolean;
  3.   next: Map<string, Node>;
  5.   constructor(isWord = false) {
  6.     this.isWord = isWord;
  7.     this.next = new Map();
  8.   }
  9. }
  11. interface TrieInterface {
  12.   root: Node;
  13.   size: number;
  14.   getSize: () => number;
  15.   add: (word: string) => void;
  16.   contains: (word: string) => boolean;
  17. }
  19. class Trie implements TrieInterface {
  20.   root = new Node();
  21.   size = 0;
  23.   getSize(): number {
  24.     return this.size;
  25.   }
  27.   /**
  28.    * 向 Trie 中添加一个新的单词 word
  29.    * @param word
  30.    */
  31.   add(word: string): void {
  32.     let current = this.root;
  34.     for (const c of word) {
  35.       if (current.next.get(c) === null) {
  36.         current.next.set(c, new Node());
  37.       }
  38.       current = current.next.get(c) as Node;
  39.     }
  41.     if (!current.isWord) {
  42.       current.isWord = true;
  43.       this.size++;
  44.     }
  45.   }
  47.   /**
  48.    * 查询单词 word 是否在 Trie 中
  49.    * @param word
  50.    */
  51.   contains(word: string): boolean {
  52.     let current = this.root;
  54.     for (const c of word) {
  55.       if (current.next.get(c) === null) {
  56.         return false;
  57.       }
  58.       current = current.next.get(c) as Node;
  59.     }
  61.     return current.isWord;
  62.   }
  64.   /**
  65.    * 查询是否在 Trie 中有单词以 prefix 为前缀
  66.    * @param prefix
  67.    */
  68.   isPrefix(prefix: string): boolean {
  69.     let cur = this.root;
  71.     for (const c of prefix) {
  72.       if (cur.next.get(c) === null) {
  73.         return false;
  74.       }
  76.       cur = cur.next.get(c) as Node;
  77.     }
  79.     return true;
  80.   }
  81. }

LeetCode 相关题目