1
00:00:01,210 --> 00:00:02,350
Welcome back.

2
00:00:02,350 --> 00:00:08,170
In the previous video, we have discussed the tabulation approach using a one dimensional array for

3
00:00:08,170 --> 00:00:10,180
solving the word break question.

4
00:00:10,180 --> 00:00:15,580
Now let's go ahead and write the pseudocode for the approach that we came up with, which is what we

5
00:00:15,580 --> 00:00:17,110
have over here okay.

6
00:00:17,110 --> 00:00:19,210
So let's write the pseudocode for this.

7
00:00:19,210 --> 00:00:22,990
So I takes the values zero up to n minus one.

8
00:00:22,990 --> 00:00:23,530
Right.

9
00:00:23,530 --> 00:00:25,540
So this is what we had previously discussed.

10
00:00:25,540 --> 00:00:27,520
So let's write a for loop for this.

11
00:00:27,520 --> 00:00:31,960
So I can say for I is equal to zero to n minus one.

12
00:00:31,960 --> 00:00:39,310
And for each place of I we are considering the substring that starts at index zero and goes up to index

13
00:00:39,310 --> 00:00:45,880
I, and we are going to check every word in the word dictionary to identify if there is a match such

14
00:00:45,880 --> 00:00:51,970
that the ending part of the substring that we are considering can be formed from a word in the word

15
00:00:51,970 --> 00:00:52,510
dictionary.

16
00:00:52,510 --> 00:00:55,810
Okay, so we'll have to go through every word in the word dictionary.

17
00:00:55,810 --> 00:00:57,820
And for that let's write a for loop.

18
00:00:57,820 --> 00:01:01,030
So I can say for word in word dictionary.

19
00:01:01,030 --> 00:01:07,360
And I will be checking if I is less than the length of the word minus one.

20
00:01:07,360 --> 00:01:10,030
Because for example, let's say we are over here.

21
00:01:10,030 --> 00:01:16,300
So the length of this substring is just two and the length of every word is greater than two, right.

22
00:01:16,300 --> 00:01:21,790
So there is no point in comparing the substring at hand with the words in our dictionary, because the

23
00:01:21,790 --> 00:01:26,890
length of the substring is lower than the length of the word we are considering in the word dictionary.

24
00:01:26,890 --> 00:01:34,120
So for that, let's say if I is less than the length of the word minus one because I is zero indexed,

25
00:01:34,120 --> 00:01:34,540
right?

26
00:01:34,540 --> 00:01:40,180
So if I less than length of the word minus one, if that is the case, then we will just continue to

27
00:01:40,180 --> 00:01:41,110
the next word.

28
00:01:41,200 --> 00:01:48,310
And if that is not the case, then we will check whether the substring that we are forming is equal

29
00:01:48,310 --> 00:01:50,050
to the word we are considering.

30
00:01:50,050 --> 00:01:56,110
And if this is true, then we will check whether this particular word is the first word of the string

31
00:01:56,110 --> 00:01:59,620
at hand, which is what we had when we got a match for hot.

32
00:01:59,620 --> 00:02:07,390
Or we will check whether the previous part in the substring can also be formed using words in dictionary,

33
00:02:07,390 --> 00:02:13,960
which is the case when we identified that the substring spot can be formed using a word from the word

34
00:02:13,960 --> 00:02:14,470
dictionary.

35
00:02:14,470 --> 00:02:20,530
And then we also saw that the previous part, which is hot, can also be formed using words in word

36
00:02:20,530 --> 00:02:20,980
dictionary.

37
00:02:20,980 --> 00:02:28,000
Okay, so if this is true and if either of these is true, that is, if the word is the first word,

38
00:02:28,000 --> 00:02:31,900
or if the previous part after removing the word at hand.

39
00:02:31,900 --> 00:02:36,160
So if the previous part can be formed using words in the dictionary.

40
00:02:36,160 --> 00:02:43,930
So if this is true and if either of these are true, then we will set depee at index I to be true.

41
00:02:43,930 --> 00:02:44,500
Okay.

42
00:02:44,500 --> 00:02:51,550
And again to identify the substring at hand for the word that we are considering, we need the indices

43
00:02:51,550 --> 00:02:59,350
starting at I minus length of the word plus one and it goes up to index I okay.

44
00:02:59,350 --> 00:03:02,470
And I is what we have from the outer for loop.

45
00:03:02,470 --> 00:03:06,250
Now for example when I is equal to two okay that's this case.

46
00:03:06,250 --> 00:03:08,440
And let's say we are considering the word hot.

47
00:03:08,440 --> 00:03:10,150
So its length is three.

48
00:03:10,150 --> 00:03:11,560
So I is two.

49
00:03:11,590 --> 00:03:15,070
So two minus three plus one gives us zero.

50
00:03:15,070 --> 00:03:18,550
So this is zero and I is equal to two okay.

51
00:03:18,550 --> 00:03:23,650
So that's how we get the substring that starts at index zero and goes up to two which is hot.

52
00:03:23,650 --> 00:03:25,840
And we see that's equal to the word.

53
00:03:25,840 --> 00:03:29,530
Let's say at that point the word in consideration is hot okay.

54
00:03:29,530 --> 00:03:36,310
So we get this substring by considering the indices that start at I minus length of the word plus one

55
00:03:36,310 --> 00:03:37,780
and goes up to I.

56
00:03:37,810 --> 00:03:38,890
So that's it.

57
00:03:38,890 --> 00:03:46,330
And once we are done filling the table over here, we just need to return the value in the last cell

58
00:03:46,330 --> 00:03:48,400
which is dp at n minus one.

59
00:03:48,400 --> 00:03:50,920
So we will just return dp at n minus one.

60
00:03:50,920 --> 00:03:56,470
And this is the tabulation approach for solving this question using a one dimensional array.