# Implement a trie with insert, search, and startsWith methods. # # Example: # # # Trie trie = new Trie();# # trie.insert("apple");# trie.search("apple"); // returns true# trie.search("app"); // returns false# trie.startsWith("app"); // returns true# trie.insert("app"); # trie.search("app"); // returns true# # # Note: # # # You may assume that all inputs are consist of lowercase letters a-z. # All inputs are guaranteed to be non-empty strings. # # Related Topics Design Trie# leetcode submit region begin(Prohibit modification and deletion)classTrie(object):def__init__(self):""" Initialize your data structure here. """ self.trie ={}definsert(self,word):""" Inserts a word into the trie. :type word: str :rtype: None """ cur = self.triefor c in word:if c notin cur: cur[c]={} cur = cur[c] cur['#']=Truedefsearch(self,word):""" Returns if the word is in the trie. :type word: str :rtype: bool """ cur = self.triefor c in word:if c notin cur:returnFalse cur = cur[c]return'#'in curdefstartsWith(self,prefix):""" Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ cur = self.triefor c in prefix:if c notin cur:returnFalse cur = cur[c]returnTrue# Your Trie object will be instantiated and called as such:# obj = Trie()# obj.insert(word)# param_2 = obj.search(word)# param_3 = obj.startsWith(prefix)# leetcode submit region end(Prohibit modification and deletion)
classTrie {staticfinalint ALPHABET_SIZE =26;staticclassTrieNode {TrieNode[] children =newTrieNode[ALPHABET_SIZE];boolean isEndOfWord;TrieNode() { isEndOfWord =false;for (int i =0; i < ALPHABET_SIZE; i++) { children[i] =null; } } }staticTrieNode root; /** Initialize your data structure here. */publicTrie() { root =newTrieNode(); } /** Inserts a word into the trie. */publicvoidinsert(String word) {int index;TrieNode node = root;for (int i =0; i <word.length(); i++) { index =word.charAt(i) -'a';if (node.children[index] ==null) {node.children[index] =newTrieNode(); } node =node.children[index]; }node.isEndOfWord=true; } /** Returns if the word is in the trie. */publicbooleansearch(String word) {TrieNode node = root;for (int i =0; i <word.length(); i++) {int index =word.charAt(i) -'a';if (node.children[index] ==null) {returnfalse; } node =node.children[index]; }returnnode.isEndOfWord; } /** Returns if there is any word in the trie that starts with the given prefix. */publicbooleanstartsWith(String prefix) {TrieNode node = root;for (int i =0; i <prefix.length(); i++) {int index =prefix.charAt(i) -'a';if (node.children[index] ==null) {returnfalse; } node =node.children[index]; }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); */