A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
-
Trie()Initializes the trie object. -
void insert(String word)Inserts the stringwordinto the trie. -
boolean search(String word)Returnstrueif the stringwordis in the trie (i.e., was inserted before), andfalseotherwise. -
boolean startsWith(String prefix)Returnstrueif there is a previously inserted stringwordthat has the prefixprefix, andfalseotherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Constraints:
1 <= word.length, prefix.length <= 2000-
wordandprefixconsist only of lowercase English letters. - At most
3 * 104calls in total will be made toinsert,search, andstartsWith.
Ideas, 建立一个TrieNode 的class, 有两个property, bool: isWord 来判断是否是一个word, dict : children 来存 c -> TrieNode.
class TrieNode: def __init__(self): self.isWord = False self.children = dict() class Trie: def __init__(self): """ Initialize your data structure here. """ self.root = TrieNode() def insert(self, word: str) -> None: """ Inserts a word into the trie. """ node = self.root for c in word: if c not in node.children: node.children[c] = TrieNode() node = node.children[c] node.isWord = True def search(self, word: str) -> bool: """ Returns if the word is in the trie. """ node = self.root for c in word: if c not in node.children: return False node = node.children[c] return node.isWord def startsWith(self, prefix: str) -> bool: """ Returns if there is any word in the trie that starts with the given prefix. """ node = self.root for c in prefix: if c not in node.children: return False node= node.children[c] return True # 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] 208. Implement Trie (Prefix Tree)_Medium tag: Trie