1
00:00:00,080 --> 00:00:00,920
Welcome back.

2
00:00:00,920 --> 00:00:05,930
We have discussed the approach that we are going to take for solving the word break question.

3
00:00:05,930 --> 00:00:11,300
And in this video, let's go ahead and write the pseudocode for the approach that we discussed.

4
00:00:11,300 --> 00:00:16,670
So for solving this question using this approach we are going to use a 2D DP array.

5
00:00:16,670 --> 00:00:18,230
That's what we have over here.

6
00:00:18,230 --> 00:00:21,560
And its size is going to be n into n.

7
00:00:21,560 --> 00:00:26,600
And initially we are just going to fill every cell with false okay.

8
00:00:26,600 --> 00:00:32,450
And then we are going to iterate through the cells in the DP table in a length wise manner.

9
00:00:32,450 --> 00:00:34,400
And again we have done this many times.

10
00:00:34,400 --> 00:00:36,890
So let's go ahead and write the pseudocode for this.

11
00:00:36,890 --> 00:00:44,510
So I can say for L taking the values from one up to n, and for I taking the values from zero up to

12
00:00:44,510 --> 00:00:45,680
n minus l.

13
00:00:45,680 --> 00:00:52,250
And for each of these combinations of l and I, j will take the value I plus l minus one.

14
00:00:52,250 --> 00:00:55,760
And again, we have discussed this many times in previous videos.

15
00:00:55,760 --> 00:01:02,570
Now once we have a combination of I and J, it represents a particular cell in this DP table over here.

16
00:01:02,570 --> 00:01:10,610
Now to see whether DP at IJ, which represents a cell in the DP table over here, has to be filled with

17
00:01:10,610 --> 00:01:18,140
the value true, which would imply that we can create that particular substring using words from the

18
00:01:18,140 --> 00:01:18,890
word dictionary.

19
00:01:18,890 --> 00:01:22,100
So to check that we will check two conditions.

20
00:01:22,100 --> 00:01:29,450
The first condition is if the substring by itself is a word in word dictionary, or if the substring

21
00:01:29,450 --> 00:01:32,660
that starts at index I and goes up to index j.

22
00:01:32,660 --> 00:01:40,340
So if this substring by itself is a word in word dictionary, then we will say dp at I j is equal to

23
00:01:40,340 --> 00:01:40,970
true.

24
00:01:41,000 --> 00:01:47,630
Now the other possibility is we are going to check all the possible partitions to see whether there

25
00:01:47,630 --> 00:01:53,300
is a partition such that dp at I k and dp at k plus one j.

26
00:01:53,300 --> 00:02:00,050
Both are true, which would mean that this part over here can be created through words in the word dictionary,

27
00:02:00,050 --> 00:02:05,630
and this substring over here can be created as well with words in the word dictionary.

28
00:02:05,630 --> 00:02:15,170
Now if this is true, it would mean that dp at I, j can also be created using words in the word dictionary,

29
00:02:15,170 --> 00:02:21,470
and for that reason we would fill dp at ij with true if we see there is such a partition.

30
00:02:21,830 --> 00:02:25,280
And again this over here just checks whether both of these are true.

31
00:02:25,280 --> 00:02:30,530
Okay, so this is how we are going to identify whether we can fill a particular cell with the value.

32
00:02:30,530 --> 00:02:30,980
True.

33
00:02:30,980 --> 00:02:35,030
And once we are done with this we would have filled all these values.

34
00:02:35,030 --> 00:02:35,420
Right.

35
00:02:35,420 --> 00:02:37,490
We have filled all these values.

36
00:02:37,700 --> 00:02:43,070
And then we would fill all these values which are of length two and in such a manner, finally, we

37
00:02:43,070 --> 00:02:44,780
would have filled this cell as well.

38
00:02:44,780 --> 00:02:51,110
And then we will just return depee at zero n minus one, which is the value in this particular cell

39
00:02:51,110 --> 00:02:51,740
over here.

40
00:02:51,740 --> 00:02:52,190
Okay.

41
00:02:52,190 --> 00:03:00,830
And again notice this cell over here represents the string that starts at H and goes up to T which is

42
00:03:00,830 --> 00:03:03,260
in fact the original problem given to us.

43
00:03:03,260 --> 00:03:08,840
And that's why returning DP at zero n minus one will give us the answer.