［leetcodeブラシノート］Implement Trie(Prefix Tree)

 1 class TrieNode {
 2     // Initialize your data structure here.
 3     char content;
 4     boolean isWord;
 5     int count;
 6     LinkedList<TrieNode> childList;
 7     
 8     public TrieNode(char c) {
 9         content = c;
10         isWord = false;
11         count = 0;
12         childList = new LinkedList<TrieNode>();
13     }
14     public TrieNode() {
15         content = ' ';
16         isWord = false;
17         count = 0;
18         childList = new LinkedList<TrieNode>();
19     }
20     
21     public TrieNode findChildC(char c){
22         if(childList != null){
23             for(TrieNode eachChild:childList){
24                 if(eachChild.content == c)
25                     return eachChild;
26             }
27         }
28         return null;
29     }
30 }
31 
32 public class Trie {
33     private TrieNode root;
34 
35     public Trie() {
36         root = new TrieNode();
37         
38     }
39 
40     // Inserts a word into the trie.
41     public void insert(String word) {
42         //if already has this word
43         if(search(word) == true)
44             return;
45         
46         TrieNode current = root;
47         for(int i = 0;i < word.length();i++){
48             TrieNode child = current.findChildC(word.charAt(i));
49             if(child == null){
50                 TrieNode temp = new TrieNode(word.charAt(i));
51                 current.childList.add(temp);
52                 current = temp;
53             }else{
54                 current = child;
55             }
56             current.count++;
57         }
58         current.isWord = true;
59     }
60 
61     // Returns if the word is in the trie.
62     public boolean search(String word) {
63         TrieNode current = root;
64         for(int i = 0;i < word.length();i++){
65             TrieNode child = current.findChildC(word.charAt(i));
66             if(child == null)
67                 return false;
68             else{
69                 current = child;
70                 continue;
71             }
72         }
73         if(current.isWord)
74             return true;
75         return false;
76     }
77 
78     // Returns if there is any word in the trie
79     // that starts with the given prefix.
80     public boolean startsWith(String prefix) {
81         TrieNode current = root;
82         for(int i = 0;i < prefix.length();i++){
83             TrieNode child = current.findChildC(prefix.charAt(i));
84             if(child == null)
85                 return false;
86             else{
87                 current = child;
88                 continue;
89             }
90         }
91         return true;
92     }
93 }
94 
95 // Your Trie object will be instantiated and called as such:
96 // Trie trie = new Trie();
97 // trie.insert("somestring");
98 // trie.search("key");