Counting Words With a Given Prefix - Leetcode 2185 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today we're solving the problem counting words with a given prefix and so the first solution I'm going to show you to this problem I think is better explained without a drawing explanation actually so I can kind of explain the intuition as I code it it's a relatively easy solution for like an easy problem there also is I would say a mediumish difficulty solution to this problem which you probably can't come up with unless you've kind of seen that pattern before but once you kind of know that pattern I think arriving at the solution isn't too difficult it just takes some practice I've practiced that pattern several times so for me it's pretty easy but for you it might take a little bit of practice I'll draw it out for you though okay so quickly just getting into what this problem is asking we're given an array of strings so example here pay attention practice attend and we're also given another a string separate from that list which is the prefix so the prefix is a t so among all of these strings we just want to count how many of them have a prefix of this a prefix if you don't know basically means it has to start at the beginning so if I have a comment over here now on the right side attention and a few of these other words and then I say my prefix is this a t I just want to know how many of these have that prefix so this one starts with a this one does not this one starts with a this one does not so we counted two of them this example doesn't perfectly illustrate it but there could have been some words like this maybe it started with an A so I guess you know that part is matching but there isn't even a second character that exists so this does not technically have a prefix of a t now we can uh think about how to solve this in the Brute Force way it's not going to be crazy pretty much just doing what I did with my like Mouse highlighting this so we're going to go over every single word so w in words and then since this is of size two we could say that is n let's get the length of the prefix so just like that that's the variable over here so we want to take the first n characters from each of these strings and we could then just do a string comparison so python makes that very very easy so that's what I'm going to be showing you down here if from the word the first n characters we can slice the string like this if you don't know these little like tips and tricks you might be interested in my python for coding interview scores I think this part might actually be covered in the python for beginners course um but then we just want to compare that with the entire prefix if this evaluates to true we can update our result which I'll uh declare here this is the count the number of matching prefixes so we will increment that like this and then after we're done we can just return that so this is how easy the problem is let me run it you can see here it works it's very efficient I think this is like the intended solution for this problem there's a couple things that I want to to note though first let me like clean this up uh from here what's the time complexity of this well we're going through every single word so let's say that's n and we're getting the first uh characters actually this might be since I'm already using n like n is the length of that prefix let me call M the number of words and then the length of the prefix that's what this comparison is doing it's just taking n characters from here because that's the length of this string and N characters from here because we only want to compare the first uh n characters so that's an O of n time operation this is technically taking extra memory since we're creating a temporary string from that word if we wanted to not do that you could solve the problem like this by using an array or not an array sorry a loop so looping over the first n characters um from the word and just a comparing so like w of I should be equal to prefix of i and if that's not the case then maybe we can break out of the loop and so one way to handle this would be like some kind of a flag out here you could use a true or false flag but I think it's fine to just use the number so I can set this increment to one we want to increment it by one like the result but if we end up reaching a case like this what we can say is well increment should then just be set to zero and then out here we can add to this whatever increment happens to be so this Loop will tell us were these words equal or not but there is a catch I believe we might get an index out of bounds error here because what if this word doesn't even have n characters remember that case where we might have a string that's just a itself well that's also not too bad to handle we could honestly just put an if statement here and just say if the length of the word is less than the length of the prefix which is n well then we can just continue to the next iteration we know they're not going to have matching prefixes so this is the same time complexity solution there's definitely more code but we're not using extra space so let me run this one so here you can see that this one works it's less efficient but in terms of Big O runtime it is as efficient okay so what's the other solution that I was going to show you well it's kind of hard to just think of from the top of your head but let me briefly explain to you or maybe remind you what the data structure called the prefix tree happens to be because once I kind of show you it will lead you to the solution so these are the words I'm going to add to my prefix tree what is a prefix tree let me just kind of show it to you so let's add this word p we're going to have a node so it's a tree where in this case we're only dealing with characters from lowercase A through Z so I'm adding this word I'm going to put it over here let's say p then I'm going to put an a after that and then I'm going to put a y now I'm going to add the word practice and now you're going to see why this is called a prefix tree because if I want to add the word practice I'm not going to put another P here why why would I do that I want all words that have the same prefix to be unified with that prefix so I want to say that I don't need to add a new P because there's already a p over there I can reuse that okay well the next character we want to add is an R it doesn't look like we have an R inserted so here I am going to add the r and then I'm going to add all the following characters I don't know if I have enough space to actually put all of them I'll try but yeah anyways I'm not going to put all of them even if I did it doesn't really matter that much so there we go what this tells us now is that here with this P we can then get all the words that start with a P so with like that prefix that's why it's called a prefix tree some people call it a try I guess you could do that but I just feel like this is like a less descriptive way of saying a prefix tree so that's why I prefer saying it this way but anyways a couple more words for us to add let's do a tend so a and then t and then another T and then an e n and wow I'm really running out of space I don't know what to do okay so this is a little bit messy but I think you probably get the idea these are supposed to be T's by the way not like the plus sign so sorry about that that's the word attend and now there's one other word attention I won't draw out the entire word but you can see we already have an A inserted we already have the two T's required for attention and we also have the E and we have the N but next we just need the t i o n so then down this path uh we could do that t IO n unfortunately this is a little bit messier than I would have expected so how is this supposed to help us anyway because we were given the prefix of a t we want to count how many words have this prefix well technically this alone won't make it super easy for us what we could do I guess is here just go down the path go down to a then go down to T and then from here just count how many paths we have how many different paths we have to like Leaf nodes or even if like there was a word that stopped somewhere in the middle for example we could have also had a word like a TT and then that would have been this word so somehow we have to mark that that was like the end of a word that is one way to do it but it's actually even easier than that as we were adding these words we could have also Associated a count with every single node so we could have said that we've inserted an a like two words that start with an A so we could have Associated an count of two with that and two here and two here here here but down here we'd put one there was only one word that actually added this D and then down this path there was also a one a one here a one here and a one here so I could do the same thing here there were two words with that P node but then there was only one word that went down here one that went down here and then one for all of these as well now that I've drawn out this prefix tree now you tell me how would we use this prefix and this tree to count the number of words that start with a t well probably just follow that path when you get to the last character then just return the count associated with that node it's possible that there actually were zero words that had this prefix imagine if we had a prefix something like uh this n o well like we don't even have the N to start with so at that point we would stop traversing and we would just return zero because we can't really go any further so that's the idea behind this if you're completely new to prefix trees you might be interested in my Advanced algorithms course where I cover it pretty in depth and then there's a several practice problems for it I think it'll probably be easier to like learn this for the first time via this or some other resource because today's problem I think is kind of a variation of the prefix tree since we are also associating a account with it okay so now to code it up assuming we already had the data structure prefix tree like assuming it was a built-in data structure the problem would be so easy it would be this easy we would just create an instance of that prefix tree and then we would go through every word and add it to that prefix tree if you want to be a little bit smarter you could even filter the words because we already know that if a word is less than like the length of it is less than the length of the prefix we don't really need that word we could skip it in other words if the length is greater than or equal to the length of the prefix only then do we care about that word then we're going to add that word so if we have that then at the end we can just call prefix tree and then assuming we Implement a count function passing in some prefix this will return to us the count of words with that prefix and then we can just go ahead and return it so now to actually implement it since we're associating a count with every single node it's going to be a little bit easier to have a separate class so I'm to call that uh prefix node and so I'll give it a Constructor that is pretty simple every node technically can have children not like one child or two child it could have up to 26 children so we could have an array for that I'm just going to use a hashmap though because I'm lazy so if we have a child suppose like a character a that's going to map to its own instance of a prefix node and we're also going to have a count associated with each initialize that as zero I think that's fine and then here we'll have a Constructor as well I don't think we actually even need it actually no we do because we are going to have to at least initialize a root so I'm going to say self. root is going to be an instance of a prefix node and technically that node is empty it doesn't have any children so that's the root it's not like an actual character I know that's kind of strange if this is the first time you're seeing a prefix tree uh being implemented that's why I think it's worth like learning how these work separately from this problem but now there's only two functions for us to add the ones that we called down here which is um add that's going to take in a word let's call that W and we're also going to have a count function which is going to take in some prefix okay so for the current word we want to add character by character so I'm going to get my root I'm going to call that Cur self. root then I'm going to go character by character in W and I've done this so many times that I already know what to do but I'll still explain it anyway there's two cases if the current node is already in current. what we want to do is then Set current equal to current. of that character which like I said it will map to some node now if it doesn't exist we'll do this else current. children for this character should map to a new instance of a prefix node and then after that we can also do the same thing that we did like we still want to then update it so you can see a little bit of repeated work there and then at the end what we would want to do is this current. count increment it by one since we are adding a new character whether it's the first time we're adding it uh down here or whether that already existed we would still want to increment the count by one so this can be cleaned up a little bit because you can see there's repeated work we're going to be doing this in both cases I can move this out and I can say only execute this part if the above is not the case so I can just get rid of that and that is pretty much it for the ad function unless I have a typo somewhere hopefully I don't but down here for counting going to be pretty similar we're going to have a current pointer which is initially going to be at the root and we're going to go character by character in the prefix and remember it's not guaranteed that all the characters from the prefix actually exist in the tree yet so we will do kind of the same thing up above if the current character is not in current. children well at that point we're not trying to insert anything at that point we can just return we can return zero because we did not find any words with the exact matching prefix otherwise we can say this current is now going to be equal to current. Children of c and once we actually reach the end suppose we actually do then this Loop would have terminated we would have gone through every character in their prefix and current should be pointing at some node and what we want to do is just return the count of that node so current. count remember count is a variable associated with every single node which we increment every time we add a character so I'll zoom out so you can see the entire code there is quite a lot of it but most of it just comes from implementing the prefix tree and then I'll scroll down you can pretty much see all of it I guess so about 33 lines of code I'm really hoping that this works and yes thankfully it does there weren't any bugs or anything but you can see it's less efficient in terms of the runtime I think that makes sense just because like most of the input sizes are going to be small so like the brute force solutions that we coded up should be pretty fast and even this like this prefix tree optimization doesn't really improve the runtime that much when you think about it because what we're doing now is just taking every single word so let's say there were M different words and for each of the words we're adding it to the try or prefix tree we're going character by character so let's say the length of the word is l and then I guess we are also going through the prefix in the worst case we'll say the length of that is n so we can add a plus n term here compare that to what we had before which was M * n and it kind of becomes clear why the new solution isn't really much more efficient because I think in most cases n is probably going to be less than the length of each word like off the top of my head I'm just thinking of a small optimization we could have done we could from here rather than going through every single character we could only go through the first n characters so maybe I can like even pass in a parameter like length to pass in and then in this function I can pass in the length of the prefix and then here rather than going character by character I could say for I in range minimum of the length of the word as well as like the length that was passed in so that we don't end up adding more than n characters from each word I don't think it'd be a massive Improvement but I think it might improve the runtime a tiny bit so we don't end up end up adding extra characters cuz for any given word we don't really care about the characters past the first n characters so that's my motivation so I think C here is going to be W of I hopefully I don't have any bugs here and let me just run this to see if it improves it okay so I ran it and it doesn't look like it made any measurable difference but I think theoretically this is slightly more efficient and it would technically be M * n + n but still you can see that the overhead of creating like a new data structure in memory creating new instance of objects which are going to be declared on the Heap is going to be less efficient than just doing a bunch of string comparisons which is what we had before anyways I think I'm probably rambling at this point most of you don't really care about these Minor Details even though I find them fascinating anyways thanks for watching if you want to learn more about prefix trees check out n code. and I'll see you pretty soon