1
00:00:00,140 --> 00:00:01,220
Welcome back.

2
00:00:01,220 --> 00:00:07,820
In the previous videos we have discussed the recursive as well as the memoization approach for solving

3
00:00:07,820 --> 00:00:13,550
this question, and we are discussing the approach number two, when we consider the two broad headings

4
00:00:13,550 --> 00:00:17,060
that we had previously discussed at the start of this question.

5
00:00:17,060 --> 00:00:17,480
Okay.

6
00:00:17,480 --> 00:00:21,110
So we had discussed the tabulation approach for approach number one.

7
00:00:21,110 --> 00:00:26,360
And then we discussed the recursive as well as memoization approach for approach number two.

8
00:00:26,390 --> 00:00:31,910
Now in this video let's get started with the tabulation approach for approach number two.

9
00:00:31,940 --> 00:00:37,610
And to discuss this let's take this example where the string given is hot spot.

10
00:00:37,610 --> 00:00:41,300
And the words in the word dictionary are hot and spot.

11
00:00:41,300 --> 00:00:41,720
Okay.

12
00:00:41,720 --> 00:00:48,770
So we will be using a one dimensional DP array which will have n cells where n is the length of the

13
00:00:48,770 --> 00:00:50,270
string which is given to us.

14
00:00:50,270 --> 00:00:55,250
And initially we will just fill every cell over here with false okay.

15
00:00:55,250 --> 00:00:58,070
And then we will have a pointer.

16
00:00:58,070 --> 00:01:03,800
Let's just call it I and I will take the values from zero up to n minus one.

17
00:01:04,070 --> 00:01:09,950
And for each value of I like let's say I is over here which is at one.

18
00:01:09,950 --> 00:01:16,160
So when I is one, we are considering the substring that starts from h and goes up to O.

19
00:01:16,160 --> 00:01:16,580
Okay.

20
00:01:16,580 --> 00:01:23,480
And let's say when I is equal to two, we will be considering the substring that starts from h and goes

21
00:01:23,480 --> 00:01:24,110
up to two.

22
00:01:24,140 --> 00:01:26,240
So this is the way that we will be proceeding.

23
00:01:26,240 --> 00:01:33,830
And for each substring we will check if there is a word ending at the character at that particular index.

24
00:01:33,830 --> 00:01:34,370
Okay.

25
00:01:34,520 --> 00:01:41,870
And for example over here when we see hot we will check whether there is a word in our dictionary which

26
00:01:41,870 --> 00:01:43,460
ends at this particular t.

27
00:01:43,460 --> 00:01:46,070
And again the word has to be an exact match.

28
00:01:46,070 --> 00:01:52,010
So when we are over here we will identify that there is a word hot in word dictionary.

29
00:01:52,010 --> 00:01:59,720
And when we see that it's a yes, we will check whether it's the first word which is the case over here.

30
00:01:59,720 --> 00:02:00,200
Okay.

31
00:02:00,200 --> 00:02:02,900
Which means there are no characters before it.

32
00:02:02,900 --> 00:02:05,180
And that's one possibility okay.

33
00:02:05,180 --> 00:02:10,940
And if there were something before it, like if you have let's say you have a character K over here.

34
00:02:10,940 --> 00:02:17,720
So if you have something before it we will check whether the previous part also can be formed using

35
00:02:17,720 --> 00:02:18,800
words in word dictionary.

36
00:02:18,800 --> 00:02:24,410
Like if you had a k over here, then it would mean that the previous part can also be formed using words

37
00:02:24,410 --> 00:02:25,400
in the dictionary.

38
00:02:25,400 --> 00:02:32,090
And if you have a yes over here and either of these is true, then we would fill true in that particular

39
00:02:32,090 --> 00:02:33,680
cell in the DP array.

40
00:02:33,680 --> 00:02:37,070
And if neither of these are true then it would stay false.

41
00:02:37,070 --> 00:02:39,980
So this is the way that we will be solving this question.

42
00:02:39,980 --> 00:02:45,650
Now the best way to see how this pans out is just to dry run the algorithm.

43
00:02:45,650 --> 00:02:46,790
So let's do that.

44
00:02:46,790 --> 00:02:50,150
So initially I is over here which is at the value zero.

45
00:02:50,150 --> 00:02:52,520
And we have only one character.

46
00:02:52,520 --> 00:02:57,080
And we see that there is no word in the word dictionary of length one.

47
00:02:57,080 --> 00:03:01,490
And therefore we just proceed to the next possible value for I.

48
00:03:01,520 --> 00:03:03,350
So I takes the value one.

49
00:03:03,350 --> 00:03:06,560
And we are considering the substring H0.

50
00:03:06,560 --> 00:03:09,920
And the length of this substring is equal to two.

51
00:03:09,920 --> 00:03:13,520
And again there is no word in the dictionary of length two.

52
00:03:13,550 --> 00:03:14,720
So we proceed.

53
00:03:14,720 --> 00:03:17,330
So I takes the value two okay.

54
00:03:17,330 --> 00:03:22,040
And at this point we are considering the substring h o t hot.

55
00:03:22,040 --> 00:03:25,370
And we see that there is a word in the dictionary hot.

56
00:03:25,370 --> 00:03:26,930
So you have a word over here.

57
00:03:26,930 --> 00:03:29,450
And we see that it's the first word okay.

58
00:03:29,450 --> 00:03:30,890
Or there is nothing before it.

59
00:03:30,890 --> 00:03:33,890
And for these reasons because we have a yes over here.

60
00:03:33,890 --> 00:03:39,050
And this is true therefore over here we are going to change this false to true.

61
00:03:41,080 --> 00:03:42,550
Now we proceed further.

62
00:03:42,550 --> 00:03:49,030
So I takes the value three and I is over here and we are considering the substring h o t s.

63
00:03:49,210 --> 00:03:54,400
And we see that there is no word in our dictionary which matches with h o s, right.

64
00:03:54,400 --> 00:04:01,840
So therefore this stays false and we proceed further and we are considering h o t s p.

65
00:04:01,870 --> 00:04:08,680
Again, there is no word in word dictionary that forms the ending part of this particular substring.

66
00:04:08,680 --> 00:04:11,920
Again, it does not need to form the complete substring.

67
00:04:11,920 --> 00:04:17,440
We just trying to see if there is a word in word dictionary that can form the ending part of this particular

68
00:04:17,440 --> 00:04:22,720
substring, like for example, if there was a word over here like s p, then we would have got a yes

69
00:04:22,720 --> 00:04:25,660
over here and we would check whether either of these is true.

70
00:04:25,660 --> 00:04:27,640
But again we are not getting that.

71
00:04:27,640 --> 00:04:29,980
And for that reason we just proceed further.

72
00:04:29,980 --> 00:04:36,850
We come over here now we are considering the substring that starts at h and goes up to O, where again

73
00:04:36,850 --> 00:04:42,880
trying to identify whether there is any word in word dictionary that can form at the ending part of

74
00:04:42,880 --> 00:04:44,140
this particular substring.

75
00:04:44,140 --> 00:04:49,780
So we have over here and when we see hot, hot does not match with O.

76
00:04:49,780 --> 00:04:55,000
And then when we come to spot we are trying to compare spot with the ending part of this substring.

77
00:04:55,000 --> 00:04:56,680
And again it does not match.

78
00:04:56,680 --> 00:04:58,690
And for that reason we proceed further.

79
00:04:58,690 --> 00:05:05,110
We come over here and when we come over here, we are considering the substring that starts at h and

80
00:05:05,110 --> 00:05:12,010
goes up to t, and we see that there is a word spot such that it matches with the ending part of the

81
00:05:12,010 --> 00:05:13,510
substring that we are considering.

82
00:05:13,510 --> 00:05:14,800
So we have spot over here.

83
00:05:14,800 --> 00:05:17,080
So that means we get a yes over here.

84
00:05:17,080 --> 00:05:20,200
And we see that this is not the first word.

85
00:05:20,200 --> 00:05:21,760
So this is not true.

86
00:05:21,760 --> 00:05:27,100
And we are checking whether the previous part can also be formed from words in word dictionary.

87
00:05:27,100 --> 00:05:33,850
And for that we just need to check the value that we have in this particular cell over here okay.

88
00:05:33,850 --> 00:05:40,240
So when we do that we see that we have true over here, which means that the previous part can be formed

89
00:05:40,240 --> 00:05:42,250
using words in word dictionary.

90
00:05:42,250 --> 00:05:45,790
And for that reason over here we are going to fill true okay.

91
00:05:45,790 --> 00:05:47,470
So this cell over here takes the value.

92
00:05:47,470 --> 00:05:47,830
True.

93
00:05:47,830 --> 00:05:49,810
And that's because we have a yes over here.

94
00:05:49,810 --> 00:05:51,340
And this is true okay.

95
00:05:51,340 --> 00:05:55,000
So this is how we were able to fill the DP table.

96
00:05:55,000 --> 00:05:59,410
And the answer will be over here which is the last cell.

97
00:05:59,410 --> 00:06:06,910
Because notice this cell represents the substring that starts at h and goes up to t which is the original

98
00:06:06,910 --> 00:06:08,860
problem which was given to us.

99
00:06:08,860 --> 00:06:12,700
So that's why whatever we fill over here will give us the answer.

100
00:06:12,700 --> 00:06:17,320
And we finally just need to return whatever we were able to fill over here.

101
00:06:17,320 --> 00:06:19,420
And in this case we are returning true.

102
00:06:19,420 --> 00:06:25,450
Which means that hot spot can be formed using words in this word dictionary over here.

103
00:06:25,450 --> 00:06:30,730
So this is the tabulation approach that we can use to solve this question.

104
00:06:30,730 --> 00:06:37,030
And notice over here we are using only a one dimensional array as opposed to a two dimensional array,

105
00:06:37,030 --> 00:06:42,160
which we had used in the previous tabulation approach for solving this question.