1
00:00:00,080 --> 00:00:06,140
Let's now go ahead and implement the tabulation approach that we have discussed in the previous video.

2
00:00:06,200 --> 00:00:06,590
Okay.

3
00:00:06,590 --> 00:00:08,270
So we are given the string s over here.

4
00:00:08,300 --> 00:00:11,660
Now let's say n is equal to s dot length.

5
00:00:12,140 --> 00:00:14,060
And we will need a DP array.

6
00:00:14,060 --> 00:00:15,830
So let's call it dp itself.

7
00:00:15,830 --> 00:00:19,100
And this array will have the same size which is n.

8
00:00:19,100 --> 00:00:24,710
And we will initially fill every cell in this array with the value false okay.

9
00:00:24,710 --> 00:00:30,800
And again we are going to make this DP array in a way that at every index this would have either the

10
00:00:30,800 --> 00:00:32,030
value true or false.

11
00:00:32,030 --> 00:00:33,860
And it will have the value true.

12
00:00:33,860 --> 00:00:40,280
If the substring that goes from zero up to that particular index can be formed using words from word

13
00:00:40,280 --> 00:00:47,660
dictionary, and therefore ultimately we would just need to return depee at n minus one, which represents

14
00:00:47,660 --> 00:00:54,020
whether the whole string, that is, the string that goes from zero up to index n minus one can be formed

15
00:00:54,020 --> 00:00:55,940
using words from word dictionary.

16
00:00:56,210 --> 00:00:56,660
All right.

17
00:00:56,690 --> 00:01:02,150
Now we are going to have a variable to iterate over the various indices of this particular depee array.

18
00:01:02,150 --> 00:01:07,880
So let I is equal to zero I less than n I plus plus okay.

19
00:01:07,940 --> 00:01:13,670
And for every value of I we are going to go through every word in the word dictionary.

20
00:01:13,670 --> 00:01:17,780
So I can say for let word of word dictionary okay.

21
00:01:18,410 --> 00:01:25,160
And our aim is to check whether we can find a word that we can fit towards the end of the substring

22
00:01:25,160 --> 00:01:27,920
that goes from zero up to index, I.

23
00:01:27,950 --> 00:01:34,730
Okay, now again, before we do that, check over here, if we find that I is less than word dot length

24
00:01:34,730 --> 00:01:40,820
minus one, then there is no point to check this and we can just continue to the next word.

25
00:01:41,540 --> 00:01:41,870
Okay.

26
00:01:41,870 --> 00:01:47,030
So we are skipping that and continuing to the next word because I itself is less than word dot length

27
00:01:47,030 --> 00:01:47,660
minus one.

28
00:01:47,780 --> 00:01:55,970
Now if this is not the case, then we will check whether the substring that can be formed in the substring

29
00:01:55,970 --> 00:01:59,120
that we are considering that goes from zero up to I.

30
00:01:59,240 --> 00:02:05,690
Okay, so we have to find the ending part of that particular substring, which has the same length as

31
00:02:05,690 --> 00:02:07,670
the length of this word over here.

32
00:02:07,670 --> 00:02:08,210
Okay.

33
00:02:08,210 --> 00:02:15,890
So for that we need to calculate the start index which would be I, which is actually the end index

34
00:02:15,890 --> 00:02:20,150
minus word dot length plus one okay.

35
00:02:20,150 --> 00:02:21,800
So that would be the start index.

36
00:02:21,800 --> 00:02:24,590
And we have to take the characters till index I.

37
00:02:24,620 --> 00:02:26,570
So that's why we have I plus one.

38
00:02:26,570 --> 00:02:32,150
Now we are going to check whether this substring over here is equal to the word that we are considering.

39
00:02:32,150 --> 00:02:41,120
Now if this is true then we are going to check either whether I is equal to word dot length minus one

40
00:02:41,300 --> 00:02:41,870
okay.

41
00:02:41,870 --> 00:02:47,780
Which would mean that this is actually the first word, or there are no characters to the left of this

42
00:02:47,780 --> 00:02:49,340
particular start index.

43
00:02:49,340 --> 00:02:56,360
So either this has to be true or if there are characters to the left of this start index, we want to

44
00:02:56,360 --> 00:03:03,590
check whether the substring that goes from zero up to the character before this start index can be formed

45
00:03:03,590 --> 00:03:10,520
using words from the word dictionary, and for that we just need to take a look at depee at I minus

46
00:03:10,520 --> 00:03:11,870
word dot length.

47
00:03:13,190 --> 00:03:15,470
Okay, so either of these has to be true.

48
00:03:15,470 --> 00:03:24,500
So if this is true and if either of these conditions is met then we can say depee at index I is equal

49
00:03:24,500 --> 00:03:25,070
to true.

50
00:03:25,070 --> 00:03:28,490
And we can just break out of this for loop okay.

51
00:03:28,490 --> 00:03:31,520
So in this manner we will fill the DP array.

52
00:03:32,630 --> 00:03:38,930
And finally once we are done with this we will come over here and we will just return DP at n minus

53
00:03:38,930 --> 00:03:39,350
one.

54
00:03:39,350 --> 00:03:40,010
All right.

55
00:03:40,010 --> 00:03:44,090
Now let's go ahead and run this code and see if it's passing all the test cases.

56
00:03:44,090 --> 00:03:47,270
But I see there's something wrong over here okay I've made a typo.

57
00:03:47,270 --> 00:03:48,470
So let's correct that.

58
00:03:48,470 --> 00:03:51,860
And let's run this code and see if it's passing all the test cases.

59
00:03:51,860 --> 00:03:53,420
And you can see that it's working.

60
00:03:53,420 --> 00:03:55,190
It's passing all the test cases.

61
00:03:55,190 --> 00:04:01,610
So this is the tabulation approach using a one dimensional array for solving the word break question.