Trie Data Structure Implementation (LeetCode)

how's it going you guys so today we are going to implement the tri data structure being able to implement this data structure is very important on leak code this question has been asked at amazon facebook google and microsoft so before i get into the video definitely like and subscribe it really helps out the channel and don't forget to check out my patreon if you want to support me further so this video is more focused on the implementation of a try rather than explaining exactly where a try is used if you want a more in-depth explanation as to what a tri data structure is i have another video explaining it and the link will be in the description but to summarize a try is a tree data structure where the nodes store letters inside of the alphabet and we can connect these nodes together to just store words inside of it so i'm going to walk through a full example as to what we have to do to implement this tri data structure we need to implement the following functions insert search and starts with our insert function will just insert a word inside of our try the search function will determine if a word is present inside of the try and lastly the starts with function will determine if a certain prefix is inside of it if we look at the notes that are provided in the problem description you can see that it says you may assume that all inputs consist of lowercase letters a to z additionally all inputs are guaranteed to be non-empty strings so the first note is very important we don't have to worry about any other letters other than just lowercase letters so each node inside of our try will have the possibility to have up to 26 children where each child is in individual lowercase letters a b c d all the way up to z so let's say we want to insert the words cats and cape inside of our try initially we're just going to have a dummy node as our root in order to insert the word cats we would create a node for each individual character in that word so we would have a new node for c a new node for a a new node for t and a new node for s and then all of these nodes would be connected together so a would be a child of c t would be a child of a and s would be a child of t as for inserting cape we can see that our first character is a c and we've already created a node c so that means we move to character a once again we've already created that node then we move to characters p and e and we have to create nodes for both of those characters node p will be connected to node a and e will be connected to p now that we've inserted both words we need to determine at which point we've actually created the words so for example if we were going down this tree data structure if we go to character a ca is not a word however when we go down to character s that would be a word at that point because we went from c-a-t-s so all we need to do is label which nodes are words so that would be character s and character e an easy way to think about this is the last character in whatever word that we're inserting will be the node that is marked as a word doing this step is very important because this is how we are going to implement our search function so for example let's say we wanted to search for the word cat we would find c find a find t but node t is not marked as a word so we would actually return false but then if we said let's search for cats we would go from c a t s and since s is marked as a word that means we would return true however the logic for the function starts with is a little bit different for example let's say we wanted to check if any word inside of our try starts with cap we would go from c to a to p and since all of those nodes in that exact path were created that means we would return true from our function okay so let's implement the code we have to implement this try class the first thing we're going to want to do is create a node class in order to store all of the individual letters so we can come down here and say class node and inside of it we're going to have a couple different attributes we're going to have obviously the character we can just call it c we're also going to have a boolean which says if the node is a word or not at that point and then finally we're going to need to store all 26 children potentially so to do this we can just use an array of size 26 so we can say node and we can call them children and then inside of our constructor we're going to be passing in our character so we can say this dot c equals c is word is just going to be initialized to false and then finally we're going to initialize our children array and this will be of size 26. the reason why it has to be 26 is because remember we're only dealing with lowercase letters so each index from 0 to 25 will be responsible for storing one character so index 0 will map to character a index 1 will map to character b index 2 to character c and so on so this children attribute is the main reason why it is considered a tree data structure because every single node is going to be pointing to up to 26 different other nodes so now that we have this class implemented we can start implementing the class try so the first thing we want to do is we need to create some sort of dummy node so we can say node root and then inside of our constructor we can say root equals new node and we can initialize the node our root to have really any character because we're not going to be using this root node so what i like to do is just do slash 0 and this pretty much just means that it's an empty character now we can start implementing our insert function the first thing we want to do is we want to keep track of a current node that we're moving through our tree data structure with so we're going to create another node and we can call it cur and this will always start at the root at the very top of our tree and now we need to loop over all of our characters so we could say in i i is less than word dot length and then inside of here we need to extract the character so we could say word char at i so this is where it kind of gets interesting we need to check if current already has a node created at character c so this will make more sense once we write it out in code so we can say if cur dot children of c minus character a if that's equal to null then we need to create the node so we'll say cur dot children c minus a equals new node of character c so the reason why we're doing c minus a is because character a has a certain decimal value so whatever character that we're getting we can always subtract it by character a and that will be an index between 0 and 25. technically we could have implemented this using like a map data structure but this is much easier to write you just have to understand why you have to subtract it by character a so if the node at that index is null then we're just creating it and this is kind of where the inserting magic happens we're creating the new node with that character c at that index once we come out of this if statement we know that that node has already been created so we can say cur equals cur children at c minus character a so this step is actually moving down the chain inside of our tree and once we come out of this for loop we're going to mark whatever our current node is we're going to say cur.is word and that is going to be equal to true the reason why we do this is because remember the very last character in whatever word that we're inserting we always need to mark that node as the word is true so now we can move on to implementing search and starts with as you can probably imagine both of these functions are very very similar so we can actually just have another helper function that both of these functions call so what we want to do in this helper function is we're going to return a node and we're going to say get node and we're going to pass in the word that we are looking for so this helper function will actually return the very last node in the word that we're looking for so you're going to see that this helper function is actually written very similarly to our insert so just like before we're going to have a node curve and we're going to start it at root and then we're going to loop over the word that we passed in so we say word dot length i plus plus just like before we're going to extract the character word char at i and now we need to check if the node at character c is even created if the node at character c is null then we just return null from this helper function because there is no node that has that path of characters so we can say if her dot children c minus character a if it's equal to null then just return null we can't move forward once we come out of this if statement just like before we need to move our curve so we'll say cur dot children c minus character a and then when we come out of the for loop all we need to do is return curve because kerr is the very last character inside of that word and now we can use this helper function to implement our search so the first thing we want to do is say node is equal to get node at the word so we're searching if that specific word is inside of our try so pretty much all we need to do is check if node is word is equal to true so we can go down here we'll say return if node is not equal to null because remember get node has the potential to return null so we have to do that check before and node is word and now for starts with it's actually even simpler we just need to make sure that the node that we're looking for is not equal to null so we can say return get node at the prefix not equal to null if the node that we return is not equal to null that must mean that the prefix was inside of our try all right so that is it for a try data structure let's just make sure that this solution works so our time complexity for insert search and starts with will all be o of m where m is the number of characters that we have inside of the word for each of these functions we have to start from our root and we're always going to go down at the maximum of what our character length is as for our space complexity our insert will be o of m where m is the number of characters we have in our word on line 15 we have to create a new node with the character so that's where the extra space comes from however for our search and starts with that is constant we do not implement any extra memory in those functions so that was the implementation of a tri data structure thank you so much for watching if you found this video useful definitely consider liking and subscribing i release video tutorials like this every single week support me on patreon if you want access to my private discord channel and with that i will see you guys in the next one

Channel: Michael Muinos

Views: 33,205

Keywords: trie data structure, implement trie leetcode, autocomplete trie, leetcode implement trie, number of islands leetcode, dynamic programming, leetcode tree questions, two sum leetcode, first missing positive leetcode, longest substring leetcode, trie data structure implementation leetcode, michael muinos, queue and stack, linked list implementation, hashmap implementation, data structures to learn

Id: giiaIofn31A

Length: 11min 50sec (710 seconds)

Published: Thu Aug 20 2020