|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +publicclassImplementTrie { |
| 4 | +classTrieNode { |
| 5 | + |
| 6 | +charval; |
| 7 | +booleanisWord; |
| 8 | +TrieNode[]children =newTrieNode[26]; |
| 9 | + |
| 10 | +// Initialize your data structure here. |
| 11 | +publicTrieNode() {} |
| 12 | + |
| 13 | +publicTrieNode(charc) { |
| 14 | +this.val =c; |
| 15 | + } |
| 16 | + } |
| 17 | + |
| 18 | +publicclassTrie { |
| 19 | +privateTrieNoderoot; |
| 20 | + |
| 21 | +publicTrie() { |
| 22 | +root =newTrieNode(); |
| 23 | +root.val =' ';//initialize root to be an empty char, this is a common practice as how Wiki defines Trie data structure as well |
| 24 | + } |
| 25 | + |
| 26 | +// Inserts a word into the trie. |
| 27 | +publicvoidinsert(Stringword) { |
| 28 | +TrieNodenode =root; |
| 29 | +for(inti =0;i <word.length();i++){ |
| 30 | +if(node.children[word.charAt(i) -'a'] ==null){ |
| 31 | +node.children[word.charAt(i) -'a'] =newTrieNode(word.charAt(i)); |
| 32 | + } |
| 33 | +node =node.children[word.charAt(i) -'a']; |
| 34 | + } |
| 35 | +node.isWord =true; |
| 36 | + } |
| 37 | + |
| 38 | +// Returns if the word is in the trie. |
| 39 | +publicbooleansearch(Stringword) { |
| 40 | +TrieNodenode =root; |
| 41 | +for(inti =0;i <word.length();i++){ |
| 42 | +if(node.children[word.charAt(i) -'a'] ==null)returnfalse; |
| 43 | +node =node.children[word.charAt(i) -'a']; |
| 44 | + } |
| 45 | +returnnode.isWord; |
| 46 | + } |
| 47 | + |
| 48 | +// Returns if there is any word in the trie |
| 49 | +// that starts with the given prefix. |
| 50 | +publicbooleanstartsWith(Stringprefix) { |
| 51 | +TrieNodenode =root; |
| 52 | +for(inti =0;i <prefix.length();i++){ |
| 53 | +if(node.children[prefix.charAt(i) -'a'] ==null)returnfalse; |
| 54 | +node =node.children[prefix.charAt(i) -'a']; |
| 55 | + } |
| 56 | +returntrue; |
| 57 | + } |
| 58 | + } |
| 59 | + |
| 60 | +// Your Trie object will be instantiated and called as such: |
| 61 | +// Trie trie = new Trie(); |
| 62 | +// trie.insert("somestring"); |
| 63 | +// trie.search("key"); |
| 64 | +} |