1 相关题目

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

Trie与简单的模式匹配问题

Trie与字符串映射

2 基本介绍

  • Trie：专门为处理字符串而设计的。
  • 查询每个条目的时间复杂度和字典中一共有多少条目无关，时间复杂度为O(w)，w为查询单词的长度。
  • 以字母为单位，将字符串拆开。
  • 每个节点有若干指向下一个节点的指针。
  • 在节点中不存储char是没有关系的。
  • 但是需要一个标识来表明当前节点是否是一个单词的结尾。

3 构造方法

  1. public class Trie {
  3.     // 节点定义
  4.     private class Node {
  6.         public boolean isWord;
  7.         public TreeMap<Character, Node> next;
  9.         public Node(boolean isWord) {
  10.             this.isWord = isWord;
  11.             next = new TreeMap<>();
  12.         }
  14.         public Node() {
  15.             this(false);
  16.         }
  17.     }
  19.     // 属性
  20.     private Node root;
  21.     private int size;
  23.     // 构造方法
  24.     public Trie() {
  25.         root = new Node();
  26.         size = 0;
  27.     }

4 插入单词

  • 一个字符一个字符插入，插入结束后需要判断当前字符是否已经是一个单词的结尾，如果是，则设置 cur.isWord = true 并进行 size++ 操作。
  1. public void add(String word) {
  2.     Node cur = root;
  4.     for (int i = 0; i < word.length(); i++) {
  5.         char c = word.charAt(i);
  6.         if (cur.next.get(c) == null)
  7.             cur.next.put(c, new Node());
  8.         cur = cur.next.get(c);
  9.     }
  11.     if (!cur.isWord) {
  12.         cur.isWord = true;
  13.         size++;
  14.     }
  15. }

5 查询单词

  • 查询到word结尾的时候需，要判断cur指向的字符是否是一个单词的结尾。
  1. public boolean contains(String word) {
  2.     Node cur = root;
  4.     for (int i = 0; i < word.length(); i++) {
  5.         char c = word.charAt(i);
  7.         if (root.next.get(c) == null)
  8.             return false;
  10.         cur = cur.next.get(c);
  11.     }
  13.     return cur.isWord;
  14. }

6 前缀搜索

  • 注意与查询单词是否存在的区别，不用判断是否是一个单词的结尾
  1. public boolean isPrefix(String prefix) {
  2.     Node cur = root;
  4.     for (int i = 0; i < prefix.length(); i++) {
  5.         char c = prefix.charAt(i);
  7.         if (cur.next.get(c) == null)
  8.             return false;
  10.         cur = cur.next.get(c);
  11.     }
  13.     return true;
  14. }

7 删除单词

  • 如果要删除的单词的结尾字符是叶子节点，则从底向上递归地删除所有next为空地节点；
  • 如果不是叶子节点，则只需要将isWord设置为false即可。

8 局限性

  • 空间问题，每个节点之存储了一个字符；
  • 解决思路：
  1. 压缩字典树：将只有一个孩子的节点合并成一个节点，但是相应的插入新单词的成本更高，操作更加复杂。
  2. 三分搜索树：