Four Semesters of Computer Science in 5 Hours, Part 2 Tries Solution

Transcript from the "Tries Solution" Lesson

[00:00:00]
>> Brian Holt: All right. So let's go ahead and implement this together. I'm gonna use the structure that I've provided here.
>> Brian Holt: Going down here to createTrie. It's gonna have a root node. And then for each one of these, I'm just gonna go through and add them to this data structure.

[00:00:23] So I'm gonna call words.forEach
>> Brian Holt: And then I'm gonna add the word to root.add(word.toLowerCase), cuz in this particular case you don't wanna worry about uppercase. So everything's gonna be auto completed in the lowercase. You can probably capital case this after you get it back, but whatever everything's gonna be lowercase for the sake of the exercise.

[00:00:55] And then we're gonna go back up to this node. And we're just gonna add a bunch of properties on this particular node, so children is gonna be an array, okay? Value of the current item is going to be an empty string, which we'll set later. I guess I probably have to put semi colons on this or it's gonna be upset.

[00:01:17] Nope, whatever.
>> Brian Holt: Terminus. This is just to say, if I finished right here, is this a word, right? Usually the answer to that is no, but sometimes it's gonna be true. And then we're gonna have a constructor. A constructor is a special function that's get run every single time this particular class is gonna get constructed.

[00:01:42] I think it follows. It's gonna take in a string. And what it's going to do is, it's going to say, first of all, this .value is going to be equal to zero or empty string, either/or. Then you're gonna say, if string.length is greater than 1, then this.children.push(new Node), and then you're gonna say string.substring From one to the end, right?

[00:02:23] So what you're doing here is if this is not the end of the word, then I'm gonna have to continue breaking it down into further and further nodes, right? That's what this does, and then I'm going to construct a new node with everything not included in the first letter, right?

[00:02:36] I don't want to include that anymore. And then you just have to know that, that means this constructors gonna be called on the smaller node in front of it, so it will continue breaking things down, right? So that's why you passed everything from one to the end, cuz it's going to keep breaking down into smaller and smaller pieces of the tree, in both sense of the word, okay.

[00:02:56] Else, if it's done, then you just say this.terminus = true
>> Brian Holt: Okay, cool.
>> Brian Holt: Okay, and then I'm gonna write an add function here.
>> Brian Holt: That's going to take in a string. And const value = string

[0]. const next = string.substring(1). And then, here I'm gonna say, if child.value triple equals value.

[00:04:08]
>> Brian Holt: There, I gotta remember exactly what this is doing. [COUGH]
>> Brian Holt: Right, so this is basically checking to see if, have I finished the string, right? Even if it still has children, have I finished the string? And if that's the case, then you need to mark the term and this is true.

[00:04:33] So in that same example, the Selena, I have to mark this as true even though that has still children to go. So if (next),
>> Brian Holt: Then child.add(next).
>> Brian Holt: Else child.terminus = true and then return at the end of all of these.
>> Brian Holt: Okay, then down here at the bottom you just say this.children.push(new Node (string)).

[00:05:17]
>> Brian Holt: Okay, cool. So that's the add function of how you add something new to a tree, right? You're basically breaking it down, piece by piece, and then creating new Nodes as you go down.
>> Brian Holt: Yep, which is fine, cool.
>> Brian Holt: Okay, so
>> Brian Holt: What I'm gonna do here with this complete thing is I'm going to return this.children

[00:06:02]
>> Brian Holt: .map
>> Brian Holt: I'm gonna say child, and then I'm gonna write an internal function called child._complete. This is my internal recursive method that I'm gonna keep calling over and over again here, child._complete(string. I'm gonna start with empty string, and an empty array. So the empty string is the string I'm gonna start with, right?

[00:06:25] And then the array is of items that I'm going to return to the user as auto complete suggestions. And then here,
>> Brian Holt: I'm going to reduce them. I'm gonna flatten them, right? We saw this before because they're gonna come back as arrays.
>> Brian Holt: Acc.concat(item), okay? So this is the flat line or smush.

[00:06:55]
>> Brian Holt: It comes up again, right? Not gonna say anything. I already did. It's fine. Okay, so now let's write the _completefunction. This takes in the search string that we're still searching for, what's already been built, and these suggestions that I already have, okay? So in this particular case, I'm asking you for up to three suggestions.

[00:07:19] So if suggestions.length is greater than or equal to 3, then stop, or search && search

[0] && =/= this.value.
>> Brian Holt: So, search string and search

[0] is not equal to this.value.
>> Brian Holt: Right, and at that point, then you're going to return the suggestions, because at that point,
>> Brian Holt: Return suggestions.

[00:08:08] At that point, that's the base case. You're gonna say if (this.terminus). So if I've reached a terminus in here, then I'm going to suggestions.push.
>> Brian Holt: I'm gonna use a template string, right, because you have to put together the current value. And the constructed string, so the built string comes first.

[00:08:29] So built, and then if I reach a terminus, right, then I'll have a built part of the string, and then I just need to concatenate this .value to it, okay?
>> Brian Holt: And right, so now I have a complete word that gets added to suggestions. And then after that, we're gonna say this .children.forEach.

[00:09:00] We're gonna go through each one of the children. So child,
>> Brian Holt: And we're just going to return child._complete. We're gonna start with search.substring(1), right? Cuz you're gonna loft that piece off.
>> Brian Holt: Okay, and then here you're gonna say that same string that we had up here. You can just even copy and paste if you want to.

[00:09:33]
>> Brian Holt: Because that's like the new build string that you're gonna keep adding one at a time, and then just put the same suggestions in there. And eventually you're gonna reach three strings or you're gonna finish the entire tree, and then you've completed. And at that point you just return suggestions.

[00:09:51]
>> Brian Holt: Okay, I think that is everything. Let me give that a shot and see if it runs.
>> Brian Holt: Nothing works. Child is not defined. At no.add.
>> Brian Holt: Did I just not pull out child, is that what I was meant to do? Yeah, that's what, sorry. Up here you say const child = this.childreni[i]

[00:10:37]
>> Brian Holt: Supposed to do up even one more. Now we try it.
>> Brian Holt: i is not defined. I was suppose to do this in a for loop. Okay, sorry, for let i = 0; i < children.length.
>> Brian Holt: this.children.length, rather, i++,
>> Brian Holt: Indent that a little bit more, okay. All right, so value string constant.substring(1) and that equals children plus plus, children i.

[00:11:50]
>> Brian Holt: If next, trial that next, [INAUDIBLE] return.
>> Brian Holt: Cuz these are all coming back to be zero which means that something's not getting added correctly. Then here in _complete,
>> Brian Holt: When I call this .children.forEach(child, child._complete substring is built and this .value. God damn it. That,
>> Brian Holt: Because it's never building anything, right?

[00:12:32] So it's just gonna blink.
>> Brian Holt: I blame all of you. I feel like you all should have caught this.
>> Speaker 2: [LAUGH]
>> Brian Holt: What do I pay you for? [LAUGH] All right, so now hopefully,
>> Brian Holt: Is it as well? That's actually probably where the real problem is.
>> Brian Holt: Well, this is hopefully at least progress.

[00:13:07]
>> Brian Holt: Now it just as built a lot. That's nice.
>> Brian Holt: All right.
>> Brian Holt: Build starts with an empty string.
>> Brian Holt: Suggestions this.terminus built this .value, which means that these probably aren't getting values where they should be. So string,
>> Brian Holt: As zero. Zero is nothing, that doesn't help. So it's string.

[00:13:42] There was multiple problems here.
>> Speaker 2: I was actually gonna ask about that, and then I didn't say anything.
>> Brian Holt: So what you're saying is that, this is your fault?
>> Speaker 2: [LAUGH]
>> Brian Holt: That's what I hear.
>> Speaker 2: Yeah, I was like why's he putting a 0 in an array and setting it to the value?

[00:13:58]
>> Brian Holt: Okay, cool. So there we found it.
>> Brian Holt: Were we rolling the whole time?
>> [INAUDIBLE]
>> Brian Holt: Okay, cool. So, we did it.
>> Brian Holt: Team effort. We got it. So, the problem was here. We weren't adding the string zero to be the value. So, there you go, now we're seeing the entire data set being added.

[00:14:26] It should handle the edge cases as well.
>> Brian Holt: See what happens. Yep, handle no match, handle Seattle, handle words that are a subset of another, like Selena's. So, cool, any questions? Before we move on.
>> Brian Holt: Awesome.