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.
The description was taken from https://leetcode.com/problems/implement-trie-prefix-tree/.
#O(M) Time, O(M) Space where M is Key Lengthclass TreeNode: def __init__(self, val) -> None: self.val = val self.children = {} self.end_here = False class Trie: def __init__(self) -> None: self.root = TreeNode(None) #O(M) Time, O(M) Space def insert(self, word: str) -> None: curr_node = self.root for char in word: if char not in curr_node.children: curr_node.children[char] = TreeNode(char) curr_node = curr_node.children[char] curr_node.end_here = True #O(M) Time, O(1) Space def search(self, word: str) -> bool: curr_node = self.root for char in word: if char not in curr_node.children: return False curr_node = curr_node.children[char] return curr_node.end_here #O(M) Time, O(1) Space def startsWith(self, prefix: str) -> bool: curr_node = self.root for char in prefix: if char not in curr_node.children: return False curr_node = curr_node.children[char] return TrueTo solve this question, we will make a Trie that consists of tree nodes.
We will start by creating our TreeNode class with its constructor.
The class will take a character value that it will use as the node's value attribute. It will have an empty dictionary for its children attribute, and a boolean value that will signify the ending of traversals and will indicate complete words.
class TreeNode: def __init__(self, val) -> None: self.val = val self.children = {} self.end_here = FalseNext, we will make our Trie class and constructor.
The constructor will initialize an empty node for the root.
class Trie: def __init__(self) -> None: self.root = TreeNode(None)
We can now make our insert function that will take a word string argument.
def insert(self, word: str) -> None:
Our function will start by setting a pointer to the root node.
curr_node = self.root
For each character in the word, we will check if the character is in the current node's children.
If not, we will create a node for the character and add it as a child.
for char in word: if char not in curr_node.children: curr_node.children[char] = TreeNode(char)
If we already have the character in the children, we will iterate to it.
curr_node = curr_node.children[char]
Once we have inserted a complete word, we will add an end_here node to signify the end of a traversal and indicate a complete word.
curr_node.end_here = True
Now we can make our search function that will take in a string word.
def search(self, word: str) -> bool:
Our function will start by setting a pointer to the root node.
curr_node = self.root
For each character in the word, we will check if the character isn't in the current node's children.
If not, we will return false because the word doesn't exist in our trie.
for char in word: if char not in curr_node.children: return False
If the character is in the current node's children, we will iterate to it.
curr_node = curr_node.children[char]
If we have traversed each character in the word, we will return if the current node has an ending node which will indicate it is a complete word and not just a prefix to a word.
return curr_node.end_here
Lastly, we will implement our startsWith function. This functionally will be nearly the same as the search function.
The only difference is we won't be looking for an ending node, as long as every character node is present within the Trie and in the same order as the prefix, we will return true.
def startsWith(self, prefix: str) -> bool: curr_node = self.root for char in prefix: if char not in curr_node.children: return False curr_node = curr_node.children[char] return True