Tire

一个字典树只要记住一个定义、两个核心操作就可以了。

son[p][u]:

  1. 其中 p 代表当前节点在树中的索引
  2. u 代表下一个子节点（字符串中的下一位）的值
  3. son[p][u]代表 下一个下一个节点在树中的索引 (0代表没有创建索引)

我们还能发现，Trie和链表的数组实现具有异曲同工之妙。

链表中 ne[idx]代表下一个节点的索引；idx代表当前节点的索引

Trie只是将它的子节点扩散成了多个

son[p][u]就相当于 ne[idx][u]

核心操作

开辟一个新节点

  1. if (!son[p][u]) son[p][u] = ++idx;

向下遍历

  1. p = son[p][u]

结合一下

  1. for(int i = 0; str[i]; ++i)
  2.     {
  3.         u = str[i] - 'a';
  4.         if(!son[p][u])son[p][u] = ++idx;
  5.         p = son[p][u];
  6.     }

这样最终的p遍历出来代表一个特定字符串的结尾。

LeetCode

实现 Trie (前缀树)

需要特别注意的是，Tire的对象实现。

Tire对象实现就比较类似于链表的类实现了。

  1. class Trie {
  2.     P head;
  3.     int idx = 0;
  4.     class P{
  5.         boolean is_end;
  6.         P[] son = new P[26];
  7.     }
  9.     /** Initialize your data structure here. */
  10.     public Trie() {
  11.         head = new P();
  12.     }
  14.     /** Inserts a word into the trie. */
  15.     public void insert(String word) {
  16.         int u = 0; 
  17.         P p = this.head;
  18.         for (int i = 0; i < word.length(); i ++){
  19.             u = word.charAt(i) - 'a';
  20.             if (p.son[u] == null) p.son[u] = new P();
  21.             p = p.son[u];
  22.         }
  23.         p.is_end = true;
  24.     }
  26.     /** Returns if the word is in the trie. */
  27.     public boolean search(String word) {
  28.         int u = 0;
  29.         P p = this.head;
  30.         for (int i = 0; i < word.length(); i ++){
  31.             u = word.charAt(i) - 'a';
  32.             if (p.son[u] == null) return false;
  33.             p = p.son[u];
  34.         }
  35.         return p.is_end;
  36.     }
  38.     /** Returns if there is any word in the trie that starts with the given prefix. */
  39.     public boolean startsWith(String prefix) {
  40.         int u = 0;
  41.         P p = this.head;
  42.         for (int i = 0; i < prefix.length(); i ++){
  43.             u = prefix.charAt(i) - 'a';
  44.             if (p.son[u] == null) return false;
  45.             p = p.son[u];
  46.         }
  47.         return true;
  48.     }
  49. }
  51. /**
  52.  * Your Trie object will be instantiated and called as such:
  53.  * Trie obj = new Trie();
  54.  * obj.insert(word);
  55.  * boolean param_2 = obj.search(word);
  56.  * boolean param_3 = obj.startsWith(prefix);
  57.  */

或者

  1. class Trie {
  2.     int idx = 0;
  3.     boolean is_end;
  4.     Trie[] son = new Trie[26];
  6.         /** Initialize your data structure here. */
  7.     public Trie() {
  9.     }
  11.     /** Inserts a word into the trie. */
  12.     public void insert(String word) {
  13.         int u = 0; 
  14.         Trie p = this;
  15.         for (int i = 0; i < word.length(); i ++){
  16.             u = word.charAt(i) - 'a';
  17.             if (p.son[u] == null) p.son[u] = new Trie();
  18.             p = p.son[u];
  19.         }
  20.         p.is_end = true;
  21.     }
  23.     /** Returns if the word is in the trie. */
  24.     public boolean search(String word) {
  25.         int u = 0;
  26.         Trie p = this;
  27.         for (int i = 0; i < word.length(); i ++){
  28.             u = word.charAt(i) - 'a';
  29.             if (p.son[u] == null) return false;
  30.             p = p.son[u];
  31.         }
  32.         return p.is_end;
  33.     }
  35.     /** Returns if there is any word in the trie that starts with the given prefix. */
  36.     public boolean startsWith(String prefix) {
  37.         int u = 0;
  38.         Trie p = this;
  39.         for (int i = 0; i < prefix.length(); i ++){
  40.             u = prefix.charAt(i) - 'a';
  41.             if (p.son[u] == null) return false;
  42.             p = p.son[u];
  43.         }
  44.         return true;
  45.     }
  46. }
  48. /**
  49.  * Your Trie object will be instantiated and called as such:
  50.  * Trie obj = new Trie();
  51.  * obj.insert(word);
  52.  * boolean param_2 = obj.search(word);
  53.  * boolean param_3 = obj.startsWith(prefix);
  54.  */