1
00:00:00,000 --> 00:00:00,900


2
00:00:00,900 --> 00:00:04,200
SPEAKER 1: Now we're ready to
check each word in the text file

3
00:00:04,200 --> 00:00:07,020
against the words in our dictionary.

4
00:00:07,020 --> 00:00:10,470
For check, you're allowed to
assume case insensitivity.

5
00:00:10,470 --> 00:00:15,090
That means that any word spelled
with any combination of uppercase

6
00:00:15,090 --> 00:00:19,680
or lowercase letters is going
to be the same, no matter what.

7
00:00:19,680 --> 00:00:21,930
You're also allowed to
assume that these strings are

8
00:00:21,930 --> 00:00:26,310
comprised of only alphabetical
characters and apostrophes.

9
00:00:26,310 --> 00:00:30,030
Let's talk about a hash
table implementation first.

10
00:00:30,030 --> 00:00:33,480
If the word indeed exists,
then it means that it

11
00:00:33,480 --> 00:00:36,375
should be found in our hash table.

12
00:00:36,375 --> 00:00:38,250
So the first thing that
we need to figure out

13
00:00:38,250 --> 00:00:42,210
is, which bucket would that word be in?

14
00:00:42,210 --> 00:00:46,620
We do that by hashing that word,
because remember-- hash functions

15
00:00:46,620 --> 00:00:47,670
are deterministic.

16
00:00:47,670 --> 00:00:52,170
They're going to return the exact
same index every time if we're

17
00:00:52,170 --> 00:00:55,060
passing in the exact same thing.

18
00:00:55,060 --> 00:00:59,580
So remembering that hash tables
are simply arrays of linked lists,

19
00:00:59,580 --> 00:01:07,180
then going to hash of word will give
you the index for your hash table.

20
00:01:07,180 --> 00:01:09,840
So now that we know which
link list to look in,

21
00:01:09,840 --> 00:01:13,410
let's talk about how we can
search within that link list.

22
00:01:13,410 --> 00:01:15,630
We'll want to iterate
over our linked list.

23
00:01:15,630 --> 00:01:19,260
And for every word, we'll want
to compare that to the word

24
00:01:19,260 --> 00:01:22,890
we're looking for, using
this function-- string case

25
00:01:22,890 --> 00:01:25,650
comp-- which is found in strings.h.

26
00:01:25,650 --> 00:01:30,630
And that will compare strings
with case insensitivity.

27
00:01:30,630 --> 00:01:34,270
Now that we know what to do
for every word in our node,

28
00:01:34,270 --> 00:01:38,520
we need to figure out how to actually
get to every node in the linked list.

29
00:01:38,520 --> 00:01:41,640
So how do we iterate over a linked list?

30
00:01:41,640 --> 00:01:46,680
Well, recall back to when
we iterate over an array.

31
00:01:46,680 --> 00:01:50,580
In our for loop, we would
have an iterator variable, i.

32
00:01:50,580 --> 00:01:52,560
So we're going to do
something very similar

33
00:01:52,560 --> 00:01:56,160
here, where we have a node pointer.

34
00:01:56,160 --> 00:01:58,660
In this case I'm going
to call it cursor.

35
00:01:58,660 --> 00:02:02,730
And I'm going to not
malloc a new node for it.

36
00:02:02,730 --> 00:02:08,020
Rather, I'm just pointing it right
at the head of my linked list.

37
00:02:08,020 --> 00:02:11,700
And so as long as my cursor
isn't pointing to null,

38
00:02:11,700 --> 00:02:15,600
I'm going to do something with the
node that cursor is pointing to.

39
00:02:15,600 --> 00:02:18,870
And then I'm going to
update my cursor, setting it

40
00:02:18,870 --> 00:02:22,290
to the next node, and the
next node, and the next,

41
00:02:22,290 --> 00:02:25,980
until the cursor points
to null, meaning that I've

42
00:02:25,980 --> 00:02:28,480
reached the end of my linked list.

43
00:02:28,480 --> 00:02:31,740
And so if I don't find the
word in that linked list,

44
00:02:31,740 --> 00:02:35,800
that means that word doesn't
belong in my dictionary.

45
00:02:35,800 --> 00:02:39,510
So now let's talk about checking
the dictionary for words

46
00:02:39,510 --> 00:02:43,380
if our dictionary is
implemented as a try.

47
00:02:43,380 --> 00:02:45,570
If the word exists in
the dictionary, then that

48
00:02:45,570 --> 00:02:48,960
means that we'll be able to
find the path in the try.

49
00:02:48,960 --> 00:02:53,070
Not only that, is_word must
be true for the last character

50
00:02:53,070 --> 00:02:57,120
in order for that to be a valid word.

51
00:02:57,120 --> 00:03:02,838
So let's talk about how we might
traverse our try, looking for a word.

52
00:03:02,838 --> 00:03:05,460
For each letter in our
input word, we'll want

53
00:03:05,460 --> 00:03:10,410
to go to the corresponding element in
children, using its alphabetical index.

54
00:03:10,410 --> 00:03:13,440
If that's null, then that
means that word is misspelled.

55
00:03:13,440 --> 00:03:15,940
The path doesn't exist.

56
00:03:15,940 --> 00:03:18,750
But if it's not null, then we
can move to the next letter.

57
00:03:18,750 --> 00:03:21,420
If we reach the end of
our input word, then we'll

58
00:03:21,420 --> 00:03:25,180
want to check if the
Boolean is_word is true.

59
00:03:25,180 --> 00:03:27,750
If it is, then great--
we found our word.

60
00:03:27,750 --> 00:03:32,480
Otherwise, that word doesn't
exist in our dictionary.

61
00:03:32,480 --> 00:03:33,622