LinkCode刷题 字典树

1. class TrieNode {  
2.     // Initialize your data structure here.  
3.     char c;  
4.     boolean leaf;  
5.     HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();  
6.       
7.     public TrieNode(char c) {  
8.         this.c = c;  
9.     }  
10.           
11.     public TrieNode(){};  
12. }  
13.   
14. public class Trie {  
15.     private TrieNode root;  
16.   
17.     public Trie() {  
18.         root = new TrieNode();  
19.     }  
20.   
21.     // Inserts a word into the trie.  
22.     public void insert(String word) {  
23.         Map<Character, TrieNode> children = root.children;  
24.         for(int i=0; i<word.length(); i++) {  
25.             char c = word.charAt(i);  
26.             TrieNode t;  
27.             if(children.containsKey(c)) {  
28.                 t = children.get(c);  
29.             } else {  
30.                 t = new TrieNode(c);  
31.                 children.put(c, t);  
32.             }  
33.             children = t.children;  
34.             if(i==word.length()-1) t.leaf=true;  
35.         }  
36.     }  
37.   
38.     // Returns if the word is in the trie.  
39.     public boolean search(String word) {  
40.         TrieNode t = searchNode(word);  
41.         return t!=null && t.leaf;  
42.     }  
43.   
44.     // Returns if there is any word in the trie  
45.     // that starts with the given prefix.  
46.     public boolean startsWith(String prefix) {  
47.         return searchNode(prefix) != null;  
48.     }  
49.       
50.     private TrieNode searchNode(String word) {  
51.         Map<Character, TrieNode> children = root.children;  
52.         TrieNode t = null;  
53.         for(int i=0; i<word.length(); i++) {  
54.             char c = word.charAt(i);  
55.             if(!children.containsKey(c)) return null;  
56.             t = children.get(c);  
57.             children = t.children;  
58.         }  
59.         return t;  
60.     }  
61. }  
62.   
63. // Your Trie object will be instantiated and called as such:  
64. // Trie trie = new Trie();  
65. // trie.insert("somestring");  
66. // trie.search("key");  

LinkCode刷题 字典树

原文：http://www.cnblogs.com/zhaoprence/p/4937702.html