classTrieNode{ boolean isWord; TrieNode[] next; publicTrieNode(){ next = new TrieNode[26]; isWord = false; } } TrieNode root; /** Initialize your data structure here. */ publicTrie(){ root = new TrieNode(); } /** Inserts a word into the trie. */ publicvoidinsert(String word){ char[] wArray = word.toCharArray(); TrieNode cur = root; for (char ch: wArray){ if (cur.next[ch - 'a'] == null){ cur.next[ch - 'a'] = new TrieNode(); cur = cur.next[ch - 'a']; } else{ cur = cur.next[ch - 'a']; } } cur.isWord = true; } /** Returns if the word is in the trie. */ publicbooleansearch(String word){ TrieNode cur = root; char[] wArray = word.toCharArray(); for (char ch: wArray){ if (cur.next[ch - 'a'] == null) returnfalse; else cur = cur.next[ch - 'a']; } return cur.isWord; } /** Returns if there is any word in the trie that starts with the given prefix. */ publicbooleanstartsWith(String prefix){ TrieNode cur = root; char[] wArray = prefix.toCharArray(); for (char ch: wArray){ if (cur.next[ch - 'a'] == null) returnfalse; else cur = cur.next[ch - 'a']; } returntrue; } }
/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */