1
00:00:00,110 --> 00:00:06,770
Let's now get into the code and implement the tabulation approach using a 2d dp array, which we have

2
00:00:06,770 --> 00:00:08,330
discussed in the previous video.

3
00:00:08,330 --> 00:00:10,820
So we are given this string s over here.

4
00:00:10,820 --> 00:00:14,540
And we are also given this word dictionary which is an array okay.

5
00:00:14,540 --> 00:00:18,350
Now let's say n is the length of the given string.

6
00:00:18,890 --> 00:00:26,600
And let's also create a DP array which will be a 2D dp array which will have n rows and n columns.

7
00:00:27,260 --> 00:00:28,880
So let's go ahead and do that.

8
00:00:30,800 --> 00:00:34,460
And we will need n columns okay.

9
00:00:34,460 --> 00:00:41,750
And what we will do is we will fill every cell in this DP array with the value false okay.

10
00:00:41,750 --> 00:00:47,780
Now let's go ahead and iterate through the cells in the DP array in a length wise manner.

11
00:00:47,780 --> 00:00:54,920
So we can say for let L is equal to one l less than equal to n l plus plus.

12
00:00:55,400 --> 00:01:06,710
And then we can say for let I is equal to zero I less than or equal to n minus n I plus plus and j is

13
00:01:06,710 --> 00:01:09,860
going to equal I plus l minus one.

14
00:01:09,860 --> 00:01:17,090
Now remember every cell in the DP table will either have the value true or false, and we will set a

15
00:01:17,090 --> 00:01:19,370
value in a particular cell to be true.

16
00:01:19,370 --> 00:01:26,450
If the substring represented by that particular cell can be formed using words from word dict.

17
00:01:26,450 --> 00:01:28,130
So that's the criteria okay.

18
00:01:28,130 --> 00:01:31,460
So we have a combination of I and j at this point.

19
00:01:31,460 --> 00:01:38,630
And we will first check whether the complete substring which goes from I to j is a word in verdict okay.

20
00:01:38,630 --> 00:01:47,300
So for that I can say if word dict dot includes s dot slice okay that's slice.

21
00:01:47,750 --> 00:01:50,150
And we have I comma j plus one.

22
00:01:50,900 --> 00:01:51,350
Okay.

23
00:01:51,350 --> 00:01:56,120
So we are checking whether the complete word is a word in the dictionary.

24
00:01:56,120 --> 00:01:59,150
And if that is true then it's pretty straightforward.

25
00:01:59,150 --> 00:02:02,450
We can just set dp at ij to be equal to true.

26
00:02:03,380 --> 00:02:09,890
But if that is not the case, then we are going to check whether we can make a partition for the substring

27
00:02:09,890 --> 00:02:16,970
such that the two partitions can be formed using words in word dictionary, and if that is possible,

28
00:02:16,970 --> 00:02:23,570
it would mean that we can form the complete substring that goes from I to j using words in the word

29
00:02:23,570 --> 00:02:24,110
dictionary.

30
00:02:24,110 --> 00:02:24,440
Okay.

31
00:02:24,440 --> 00:02:32,150
And again for this we will use another variable and for let k is equal to I k less than j k plus plus.

32
00:02:32,150 --> 00:02:36,290
So notice k takes values from I up to j minus one.

33
00:02:36,290 --> 00:02:40,700
And again this is the same thing that we did in the palindrome partitioning question okay.

34
00:02:40,700 --> 00:02:52,400
And over here we will say dp at I j is equal to dp at I j or the partitioning okay, which is dp at

35
00:02:52,400 --> 00:03:01,100
I k and dp at k plus one j okay.

36
00:03:01,100 --> 00:03:06,770
And again notice it's important that we have and over here because we need both these parts to be true.

37
00:03:06,770 --> 00:03:10,700
Only then it would mean that DP at I j can be set to true.

38
00:03:10,700 --> 00:03:16,940
Because if both these parts can be formed using words in the dictionary, then the substring that goes

39
00:03:16,940 --> 00:03:21,140
from I to j can also be formed using words in word dictionary.

40
00:03:21,350 --> 00:03:22,550
Okay, so that's it.

41
00:03:22,550 --> 00:03:29,240
Now once we are out of this for loop, we would just need to return dp at zero n minus one okay.

42
00:03:29,240 --> 00:03:35,930
And again notice the cell zero n minus one in the dp table represents the substring that goes from index

43
00:03:35,930 --> 00:03:41,180
zero up to index n minus one, which in fact is the input string which is given to us.

44
00:03:41,180 --> 00:03:41,570
Right.

45
00:03:41,570 --> 00:03:43,820
So that's why this cell will hold the answer.

46
00:03:43,820 --> 00:03:48,020
Now let's go ahead and run this code and see if it's passing all the test cases.

47
00:03:49,250 --> 00:03:50,870
And you can see that it's working.

48
00:03:50,870 --> 00:03:52,700
It's passing all the test cases.