定义

Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：

  • 指向子节点的指针数组 children。数组长度为 26，即小写英文字母的数量。此时 children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。
  • 布尔字段 isEnd，表示该节点是否为字符串的结尾

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

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

给出一组单词，inn, int, at, age, adv,ant, adv 我们可以得到下面的Trie：
image.png

题目：208. 实现 Trie (前缀树) - 力扣（LeetCode）

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

（实现代码写的比较粗糙……看个意思就行）

HashMap实现

  1. class Trie {
  3.     public String value;
  4.     public Map<Character, Trie> children;
  5.     public boolean isEnd;
  7.     public Trie() {
  8.         this.value = null;
  9.         this.isEnd = false;
  10.         this.children = new HashMap<>();
  11.     }
  13.     public void insert(String word) {
  14.         if (search(word)) return;
  16.         char []str = word.toCharArray();
  17.         int len = str.length;
  18.         int i;
  19.         Trie currentTrie = new Trie();
  20.         Map<Character, Trie> ths = this.children;
  21.         for (i = 0; i < len; i++){
  22.             if (ths.containsKey(str[i])) {
  23.                 currentTrie = ths.get(str[i]);
  24.                 ths = ths.get(str[i]).children;
  25.             }
  26.             else {
  27.                 Trie newTire = new Trie();
  28.                 ths.put(str[i], newTire);
  29.                 ths = newTire.children;
  30.                 if (i == len - 1){
  31.                     newTire.value = word;
  32.                     newTire.isEnd = true;
  33.                     return;
  34.                 }
  35.             }
  36.         }
  37.         if (!currentTrie.isEnd) currentTrie.value = word;
  39.     }
  41.     public boolean search(String word) {
  42.         if (find(word) != null) return true;
  43.         return false;
  44.     }
  46.     private String find (String word){
  47.         char []str = word.toCharArray();
  48.         int len = str.length;
  49.         int i;
  50.         String res = null;
  51.         Map<Character, Trie> ths = this.children;
  52.         for (i = 0; i < len; i++){
  53.             if (ths.containsKey(str[i])) {
  54.                 res = ths.get(str[i]).value;
  55.                 ths = ths.get(str[i]).children;
  56.             }
  57.             else break;
  58.         }
  59.         if (i != len) res = null;
  60.         return res;
  61.     }
  63.     public boolean startsWith(String prefix) {
  64.         char []str = prefix.toCharArray();
  65.         int len = str.length;
  66.         int i;
  67.         Map<Character, Trie> ths = this.children;
  68.         for (i = 0; i < len; i++){
  69.             if (ths.containsKey(str[i])) {
  70.                 ths = ths.get(str[i]).children;
  71.             }
  72.             else break;
  73.         }
  74.         if (i == len) return true;
  75.         return false;
  76.     }
  77. }
  79. /**
  80.  * Your Trie object will be instantiated and called as such:
  81.  * Trie obj = new Trie();
  82.  * obj.insert(word);
  83.  * boolean param_2 = obj.search(word);
  84.  * boolean param_3 = obj.startsWith(prefix);
  85.  */

数组实现

  1. class Trie {
  3.     public String value;
  4.     public Trie[] nodes;
  5.     public boolean isEnd;
  7.     public Trie() {
  8.         this.nodes = new Trie[26];
  9.         this.value = null;
  10.         this.isEnd = false;
  11.     }
  13.     public void insert(String word) {
  14.         char[] str = word.toCharArray();
  15.         Trie currentTrie = this;
  16.         for (char c : str){
  17.             if (currentTrie.nodes[c-'a'] == null) currentTrie.nodes[c-'a'] = new Trie();
  18.             currentTrie = currentTrie.nodes[c-'a'];
  19.         }
  20.         currentTrie.isEnd = true;
  21.         currentTrie.value = word;
  22.     }
  24.     public boolean search(String word) {
  25.         char[] str = word.toCharArray();
  26.         Trie currentTrie = this;
  27.         for (char c : str){
  28.             if (currentTrie.nodes[c-'a'] == null) return false;
  29.             currentTrie = currentTrie.nodes[c-'a'];
  30.         }
  31.         return currentTrie.isEnd;
  32.     }
  34.     public boolean startsWith(String prefix) {
  35.         char[] str = prefix.toCharArray();
  36.         Trie currentTrie = this;
  37.         for (char c : str){
  38.             if (currentTrie.nodes[c-'a'] == null) return false;
  39.             currentTrie = currentTrie.nodes[c-'a'];
  40.         }
  41.         return true;
  42.     }
  43. }
  45. /**
  46.  * Your Trie object will be instantiated and called as such:
  47.  * Trie obj = new Trie();
  48.  * obj.insert(word);
  49.  * boolean param_2 = obj.search(word);
  50.  * boolean param_3 = obj.startsWith(prefix);
  51.  */