LeetCode 208. Implement Trie (Prefix Tree)

原题链接在这里：https://leetcode.com/problems/implement-trie-prefix-tree/

题目：

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

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

题解：

Trie 是一种数据结构，用来做字典查找，是一种用于快速检索的多叉数结构。例如，英文字母的字典树是26叉数，数字的字典树是10叉树。

Trie树的基本性质有三点，归纳为：

根节点不包含字符，根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符串不相同。

下面有两种方法，第一种相对简洁

Time Complexity: insert, O(m). search, O(m). startsWith, O(m). m = word.length().

Space: O(n*m). n是总共有多少词.

AC Java:

 1 class Trie {
 2     TrieNode root;
 3     
 4     /** Initialize your data structure here. */
 5     public Trie() {
 6         root = new TrieNode();
 7     }
 8     
 9     /** Inserts a word into the trie. */
10     public void insert(String word) {
11         TrieNode p = root;
12         for(char c : word.toCharArray()){
13             if(p.next[c-'a'] == null){
14                 p.next[c-'a'] = new TrieNode();
15             }
16             
17             p = p.next[c-'a'];
18         }
19         
20         p.val = word;
21     }
22     
23     /** Returns if the word is in the trie. */
24     public boolean search(String word) {
25         TrieNode p = root;
26         for(char c : word.toCharArray()){
27             if(p.next[c-'a'] == null){
28                 return false;
29             }
30             
31             p = p.next[c-'a'];
32         }
33         
34         return p.val.equals(word);
35     }
36     
37     /** Returns if there is any word in the trie that starts with the given prefix. */
38     public boolean startsWith(String prefix) {
39         TrieNode p = root;
40         for(char c : prefix.toCharArray()){
41             if(p.next[c-'a'] == null){
42                 return false;
43             }
44             
45             p = p.next[c-'a'];
46         }
47         
48         return true;
49     }
50 }
51 
52 class TrieNode{
53     String val;
54     TrieNode [] next;
55     
56     public TrieNode(){
57         val = "";
58         next = new TrieNode[26];
59     }
60 }
61 
62 /**
63  * Your Trie object will be instantiated and called as such:
64  * Trie obj = new Trie();
65  * obj.insert(word);
66  * boolean param_2 = obj.search(word);
67  * boolean param_3 = obj.startsWith(prefix);
68  */

第二种方法用的是存是否为叶子节点. 与第一种方法的存val不同，但本质上都是一回事。

Note: search() 和 startsWith() 有所不同，search时还需要注意跳出loop时是否已经打了Trie树的叶子节点.

AC Java:

 1 class TrieNode {
 2     //Mark if this node is the end of the word
 3     boolean isLeaf;
 4     HashMap<Character,TrieNode> nexts;
 5     public TrieNode() {
 6         nexts = new HashMap<Character,TrieNode>();
 7     }
 8 }
 9 
10 public class Trie {
11     private TrieNode root;
12     
13     public Trie() {
14         root = new TrieNode();
15     }
16 
17     // Inserts a word into the trie.
18     public void insert(String word) {
19         TrieNode p = root;
20         char [] s = word.toCharArray();
21         int len = s.length;
22         int i = 0;
23         //traverse the existing character
24         while(i<len){
25             if(p.nexts.containsKey(s[i])){
26                 p = p.nexts.get(s[i]);
27                 i++;
28             }else{
29                 break;
30             }
31         }
32         //append new nodes
33         while(i<len){
34             TrieNode newNode = new TrieNode();
35             p.nexts.put(s[i],newNode);
36             p = newNode;
37             i++;
38         }
39         //Set the end of the word
40         p.isLeaf = true;
41     }
42 
43     // Returns if the word is in the trie.
44     public boolean search(String word) {
45         TrieNode p = root;
46         char [] s = word.toCharArray();
47         int len = s.length;
48         int i = 0;
49         while(i<len){
50             TrieNode nextNode = p.nexts.get(s[i]);
51             if(nextNode == null){
52                 return false;
53             }
54             p = nextNode;
55             i++;
56         }
57         //return if this is a leaf node
58         return p.isLeaf;
59     }
60 
61     // Returns if there is any word in the trie
62     // that starts with the given prefix.
63     public boolean startsWith(String prefix) {
64         TrieNode p = root;
65         char [] s = prefix.toCharArray();
66         int len = s.length;
67         int i = 0;
68         while(i<len){
69             TrieNode nextNode = p.nexts.get(s[i]);
70             if(nextNode == null){
71                 return false;
72             }
73             p = nextNode;
74             i++;
75         }
76         return true;
77     }
78 }
79 
80 // Your Trie object will be instantiated and called as such:
81 // Trie trie = new Trie();
82 // trie.insert("somestring");
83 // trie.search("key");

Reference: http://blog.csdn.net/wzy_1988/article/details/45744067#trie树基本实现