Trie
Implement Trie Methods
medium
Count: 10
DESCRIPTION
Implement the search, startsWith, and delete methods of a Trie.
- search(word) returns true if the word is in the Trie, and false otherwise.
- startsWith(prefix) returns true if any word in the Trie starts with the given prefix, and false otherwise.
- delete(word) removes the word from the Trie, and does not return a value.
The creation of the Trie and the insert method are already implemented for you.
The test cases include two parameters:
- initialWords: a list of words to add to the Trie,
- commands: a list of commands to run. Each command is a tuple, where the first element is "search", "startsWith", or "delete", and the second element is the word or prefix.
The test cases will create the Trie with the initial words, and then run the commands in order, and compare the output to the expected output. Note we only compare the output of search and startsWith commands, not delete commands.
Input:
initialWords = ["apple", "app", "apartment"] commands = [ ["search", "apple"], ["search", "apartment"], ["search", "appl"], ["delete", "app"], ["search", "app"], ]
Output: [True, True, False, False]
Explanation:
Trie.search("apple") -> True Trie.search("apartment") -> True Trie.search("appl") -> False Trie.delete("app") -> None # Return value not checked Trie.search("app") -> False
Explanation
Search
- To search for a word in a trie, we start from the root node and check if the current node has a child corresponding to the first character of the word.
- If it does, we move to the child node and repeat the process with the next character.
- If we reach the end of the word, we check if the current node is a leaf node. If it is, the word exists in the trie.
- If the word does not exist in the trie, we return false.
Solution
Python
def search(self, word: str) -> bool:node = self.rootfor char in word:if char not in node.children:return Falsenode = node.children[char]return node.is_end_of_word
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.