1
00:00:00,230 --> 00:00:01,400
Welcome back.

2
00:00:01,400 --> 00:00:06,170
Now this is the recursive approach that we have coded in the previous video.

3
00:00:06,170 --> 00:00:08,330
Now let's go ahead and memorize this.

4
00:00:08,330 --> 00:00:10,640
And for this we will need a DP array.

5
00:00:10,760 --> 00:00:12,770
Let's just call it DP itself.

6
00:00:12,770 --> 00:00:16,010
And this is going to be an array of size n.

7
00:00:16,530 --> 00:00:21,420
And we will fill every cell in this array over here with the value minus one.

8
00:00:21,720 --> 00:00:22,170
Okay.

9
00:00:22,170 --> 00:00:28,620
Now in the Czech ending at function over here after checking the base case, before we go ahead and

10
00:00:28,620 --> 00:00:36,840
do these computations over here, we will check if depee at index is not equal to minus one, because

11
00:00:36,840 --> 00:00:42,210
if it's not minus one, the reason for this would be that we have already previously calculated and

12
00:00:42,210 --> 00:00:43,080
stored it over here.

13
00:00:43,080 --> 00:00:48,270
Because notice initially we had filled every cell in the DP array with the value minus one.

14
00:00:48,270 --> 00:00:48,630
Okay.

15
00:00:48,630 --> 00:00:54,060
So if this is true then we can just return dp at index.

16
00:00:54,060 --> 00:00:56,730
And we do not need to do any of these computations.

17
00:00:56,730 --> 00:01:01,710
But if that is not the case, then we come over here and we do all of this.

18
00:01:01,710 --> 00:01:04,770
And before we return true we are going to store it.

19
00:01:04,770 --> 00:01:05,070
Okay.

20
00:01:05,070 --> 00:01:09,000
So I can say DP at index is equal to true.

21
00:01:09,000 --> 00:01:12,300
And then we can return either dp at index or true.

22
00:01:12,300 --> 00:01:13,440
It does not matter okay.

23
00:01:13,440 --> 00:01:17,160
But let me just change this to return dp at index.

24
00:01:17,160 --> 00:01:19,620
Now over here we have false.

25
00:01:19,620 --> 00:01:22,830
And again before returning false we have to store it.

26
00:01:22,830 --> 00:01:26,490
So I can say dp at index is equal to false.

27
00:01:26,490 --> 00:01:30,420
And then we can just return dp at index okay.

28
00:01:30,420 --> 00:01:31,260
So that's it.

29
00:01:31,260 --> 00:01:35,460
So just by adding a few lines of code we were able to memorize this.

30
00:01:35,460 --> 00:01:39,990
Now let's go ahead and run this code and see if it's passing all the test cases.

31
00:01:41,790 --> 00:01:43,500
And you can see that it's working.

32
00:01:43,500 --> 00:01:45,090
It's passing all the test cases.

33
00:01:45,090 --> 00:01:48,930
So this is the memoization approach for solving the word break question.