* Trie.java * Created by shenhuaze on 2018/5/20. */ publicclassTrie{ TrieNode root; publicTrie(){ // do intialization if necessary root = new TrieNode(); }
/* * @param word: a word * @return: nothing */ publicvoidinsert(String word){ // write your code here TrieNode curr = root; for (int i = 0; i < word.length(); i++) { int offset = word.charAt(i) - 'a'; if (curr.children[offset] == null) { curr.children[offset] = new TrieNode(); } curr = curr.children[offset]; } curr.isLeaf = true; }
/* * @param word: A string * @return: if the word is in the trie. */ publicbooleansearch(String word){ // write your code here TrieNode curr = root; for (int i = 0; i < word.length(); i++) { int offset = word.charAt(i) - 'a'; if (curr.children[offset] == null) { returnfalse; } curr = curr.children[offset]; } return curr.isLeaf; }
/* * @param prefix: A string * @return: if there is any word in the trie that starts with the given prefix. */ publicbooleanstartsWith(String prefix){ // write your code here TrieNode curr = root; for (int i = 0; i < prefix.length(); i++) { int offset = prefix.charAt(i) - 'a'; if (curr.children[offset] == null) { returnfalse; } curr = curr.children[offset]; } returntrue; } }
1 2 3 4 5 6 7 8 9 10 11 12 13
* DemoTest.java * Created by shenhuaze on 2018/5/20. */ publicclassDemoTest{ publicstaticvoidmain(String[] args){ Trie trie = new Trie(); trie.insert("hello"); System.out.println(trie.search("hello")); System.out.println(trie.startsWith("hell")); System.out.println(trie.search("world")); } }
近期评论