Leetcode: Implement Trie (Prefix Tree) && Summary: Trie

Implement a trie with insert, search, and startsWith methods.

Note:

You may assume that all inputs are consist of lowercase letters a-z.

参考百度百科：Trie树

a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes)

The time complexity to insert and to search is O(m), where m is the length of the string.

标准Trie树的应用和优缺点

(1) 全字匹配：确定待查字串是否与集合的一个单词完全匹配。如上代码fullMatch()。

(2) 前缀匹配：查找集合中与以s为前缀的所有串。

注意：Trie树的结构并不适合用来查找子串。这一点和前面提到的PAT Tree以及后面专门要提到的Suffix Tree的作用有很大不同。

优点：查找效率比与集合中的每一个字符串做匹配的效率要高很多。在o(m)时间内搜索一个长度为m的字符串s是否在字典里。Predictable O(k) lookup time where k is the size of the key

缺点：标准Trie的空间利用率不高，可能存在大量结点中只有一个子结点，这样的结点绝对是一种浪费。正是这个原因，才迅速推动了下面所讲的压缩trie的开发。

什么时候用Trie?

It all depends on what problem you're trying to solve. If all you need to do is insertions and lookups, go with a hash table. If you need to solve more complex problems such as prefix-related queries, then a trie might be the better solution.

像word search II就是跟前缀有关，如果dfs发现当前形成的前缀都不在字典中，就没必要再搜索下去了，所以用trie不用hashSet

Easy version of implement Trie. TrieNode only contains TrieNode[] children, and boolean isWord two fields

 class Trie {

     class TrieNode {

         TrieNode[] children;

         boolean isWord;

         public TrieNode() {

             this.children = new TrieNode[26];

             this.isWord = false;

         }

     }

     TrieNode root;

     /** Initialize your data structure here. */

     public Trie() {

         this.root = new TrieNode();

     }

     /** Inserts a word into the trie. */

     public void insert(String word) {

         if (word == null || word.length() == 0) return;

         TrieNode cur = this.root;

         for (int i = 0; i < word.length(); i ++) {

             if (cur.children[word.charAt(i) - 'a'] == null) {

                 cur.children[word.charAt(i) - 'a'] = new TrieNode();

             }

             cur = cur.children[word.charAt(i) - 'a'];

         }

         cur.isWord = true;

     }

     /** Returns if the word is in the trie. */

     public boolean search(String word) {

         TrieNode cur = this.root;

         for (int i = 0; i < word.length(); i ++) {

             if (cur.children[word.charAt(i) - 'a'] == null) return false;

             cur = cur.children[word.charAt(i) - 'a'];

         }

         return cur.isWord;

     }

     /** Returns if there is any word in the trie that starts with the given prefix. */

     public boolean startsWith(String prefix) {

         TrieNode cur = this.root;

         for (int i = 0; i < prefix.length(); i ++) {

             if (cur.children[prefix.charAt(i) - 'a'] == null) return false;

             cur = cur.children[prefix.charAt(i) - 'a'];

         }

         return true;

     }

 }

Older version, TrieNode also has num and val fields, which might not be that useful.

 class TrieNode {

     // Initialize your data structure here.

     int num; //How many words go through this TrieNode

     TrieNode[] son; //collection of sons

     boolean isEnd;

     char val;

     public TrieNode() {

         this.num = 0;

         this.son = new TrieNode[26];

         this.isEnd = false;

     }

 }

 public class Trie {

     private TrieNode root;

     public Trie() {

         root = new TrieNode();

     }

     // Inserts a word into the trie.

     public void insert(String word) {

         if (word==null || word.length()==0) return;

         char[] arr = word.toCharArray();

         TrieNode node = this.root;

         for (int i=0; i<arr.length; i++) {

             int pos = (int)(arr[i] - 'a');

             if (node.son[pos] == null) {

                 node.son[pos] = new TrieNode();

                 node.son[pos].num++;

                 node.son[pos].val = arr[i];

             }

             else {

                 node.son[pos].num++;

             }

             node = node.son[pos];

         }

         node.isEnd = true;

     }

     // Returns if the word is in the trie.

     public boolean search(String word) {

         char[] arr = word.toCharArray();

         TrieNode node = this.root;

         for (int i=0; i<arr.length; i++) {

             int pos = (int)(arr[i] - 'a');

             if (node.son[pos] == null) return false;

             node = node.son[pos];

         }

         return node.isEnd;

     }

     // Returns if there is any word in the trie

     // that starts with the given prefix.

     public boolean startsWith(String prefix) {

         char[] arr = prefix.toCharArray();

         TrieNode node = this.root;

         for (int i=0; i<arr.length; i++) {

             int pos = (int)(arr[i] - 'a');

             if (node.son[pos] == null) return false;

             node = node.son[pos];

         }

         return true;

     }

 }

 // Your Trie object will be instantiated and called as such:

 // Trie trie = new Trie();

 // trie.insert("somestring");

 // trie.search("key");

巴特西

Leetcode: Implement Trie (Prefix Tree) && Summary: Trie

最新文章

热门文章