1
00:00:00,170 --> 00:00:03,470
So let's get started with approach number one.

2
00:00:03,470 --> 00:00:06,590
Now to discuss this, let's take an example.

3
00:00:06,590 --> 00:00:10,490
Let's say the string which is given to us is hot spot.

4
00:00:10,490 --> 00:00:15,590
And the word dictionary has the words hot and spot.

5
00:00:16,010 --> 00:00:21,860
Now to see whether we can form the given string using words from word dictionary.

6
00:00:21,860 --> 00:00:23,810
And again that's the question at hand.

7
00:00:23,810 --> 00:00:31,880
We will use a two dimensional DP array where we have rows as well as columns for every character in

8
00:00:31,880 --> 00:00:32,870
the given string.

9
00:00:32,870 --> 00:00:39,320
Okay, so notice over here I have hot spot on the columns as well as on the rows.

10
00:00:39,350 --> 00:00:45,020
Now what we will do is we will iterate over each possible substring.

11
00:00:45,020 --> 00:00:48,710
And we know how to do that by iterating length wise.

12
00:00:48,710 --> 00:00:55,130
And then for every cell which represents a particular substring, we will check whether that particular

13
00:00:55,130 --> 00:00:57,500
substring is in word dictionary.

14
00:00:57,500 --> 00:01:03,410
So if that particular substring, the whole substring is a word in word dictionary, we will just fill

15
00:01:03,410 --> 00:01:05,240
true in that particular cell.

16
00:01:05,240 --> 00:01:13,250
And if this is not the case then we will check whether we can form that particular substring using words

17
00:01:13,250 --> 00:01:14,840
from word dictionary okay.

18
00:01:14,840 --> 00:01:19,130
And for that we will have another variable k which goes from I to j.

19
00:01:19,130 --> 00:01:22,940
And again this is the partition method that we have discussed in the previous questions.

20
00:01:22,940 --> 00:01:31,100
And if we see that depee at I, k and depee at k plus one j, both of these are true.

21
00:01:31,100 --> 00:01:34,550
Then we will mark depee at I j as true.

22
00:01:34,550 --> 00:01:40,130
Again, we have seen this many times in previous questions, so what we are doing is to identify whether

23
00:01:40,130 --> 00:01:44,660
dp at I, j is true or false.

24
00:01:45,050 --> 00:01:51,740
We are trying all possible partitions and for that we have another variable k and k takes the values

25
00:01:51,740 --> 00:01:54,170
from I up to j minus one.

26
00:01:54,170 --> 00:01:54,530
Okay.

27
00:01:54,530 --> 00:02:00,140
So again this has to be j minus one if you consider these as values taken by k.

28
00:02:00,140 --> 00:02:06,650
But again in some programming languages, if you write k in range I to j, it means that k takes values

29
00:02:06,650 --> 00:02:08,330
from I up to j minus one.

30
00:02:08,330 --> 00:02:14,780
So k takes values from I up to j minus one, and for each value of k we are making a partition.

31
00:02:14,780 --> 00:02:21,770
For example, when k is I, this becomes depee at I I, which is just one character, and this becomes

32
00:02:21,770 --> 00:02:23,780
dp at I plus one till j.

33
00:02:23,780 --> 00:02:24,260
Okay.

34
00:02:24,260 --> 00:02:29,030
And what we are checking over here is we are checking whether this is true and this is true.

35
00:02:29,030 --> 00:02:36,500
So if both of these are true it means that dp at I k can be formed from the words in our dictionary,

36
00:02:36,500 --> 00:02:39,500
or is a word in itself which is there in word dictionary.

37
00:02:39,500 --> 00:02:47,780
And if dp at k plus one j is true, it means that this substring can be formed from words in word dictionary.

38
00:02:47,780 --> 00:02:55,820
And if these two are true, it would mean that dp at I j can be formed from words in word dictionary.

39
00:02:55,820 --> 00:02:58,520
Okay, so this is the logic that we are going to use.

40
00:02:58,520 --> 00:03:05,240
And again we have done this previously where we used a variable k to make all the possible partitions.

41
00:03:05,240 --> 00:03:09,680
And once we have done this and again let's quickly take an example.

42
00:03:09,680 --> 00:03:15,680
For example, if we take a look at this cell over here, this cell would represent the substring that

43
00:03:15,680 --> 00:03:18,950
starts at h and goes up to t which is hot.

44
00:03:18,950 --> 00:03:22,610
And we see that hot is a word in word dictionary.

45
00:03:22,610 --> 00:03:26,480
So we would be filling true over here because of this criteria.

46
00:03:26,510 --> 00:03:28,970
Now what about this cell over here.

47
00:03:28,970 --> 00:03:35,360
This cell represents the substring that starts at O and goes up to S okay.

48
00:03:35,360 --> 00:03:36,800
So that's o t s.

49
00:03:36,800 --> 00:03:44,300
Now over here when we check this criteria we see that o t s is not a word in the dictionary in itself.

50
00:03:44,300 --> 00:03:46,910
And therefore this is not true.

51
00:03:46,910 --> 00:03:47,330
Okay.

52
00:03:47,330 --> 00:03:49,010
And then we check this part over here.

53
00:03:49,010 --> 00:03:56,090
We make all the possible partitions to see whether we can get a partition such that dp at ik and DP

54
00:03:56,090 --> 00:03:57,080
at k plus one j.

55
00:03:57,080 --> 00:03:58,160
Both are true.

56
00:03:58,160 --> 00:04:04,250
And in the case of OTS we will see that's not true and therefore over here we would be filling false

57
00:04:04,250 --> 00:04:04,760
okay.

58
00:04:04,760 --> 00:04:11,090
And again similarly if you consider this cell over here it starts at H and goes up to S which is hots.

59
00:04:11,090 --> 00:04:14,990
And again hots is not a word in itself which is there in word visionary.

60
00:04:14,990 --> 00:04:20,030
And there is no partition such that dp at ik and DP at k plus one j become true.

61
00:04:20,030 --> 00:04:26,120
Okay, so you have hots and this not being true means there is no partition like you.

62
00:04:26,120 --> 00:04:31,100
If you make a partition like this, you see hot is there in your dictionary, but S is not there in

63
00:04:31,100 --> 00:04:31,850
word dictionary.

64
00:04:31,850 --> 00:04:38,090
Okay, so there is no partition such that the partitioned parts could be made through words in word

65
00:04:38,090 --> 00:04:38,600
dictionary.

66
00:04:38,600 --> 00:04:42,800
And for that reason over here also we will be filling false.

67
00:04:42,800 --> 00:04:48,530
So again I'm not going to dry run this because this is pretty similar to what we discussed in previous

68
00:04:48,530 --> 00:04:49,850
questions in this section.

69
00:04:49,850 --> 00:04:55,940
And once we have iterated through all the possible substrings, we will get our answer over here in

70
00:04:55,940 --> 00:04:56,450
this cell.

71
00:04:56,450 --> 00:04:59,720
Because notice this cell represents the substring.

72
00:04:59,980 --> 00:05:05,500
That starts at H and goes up to T, which is in fact the string given to us.

73
00:05:05,500 --> 00:05:12,310
So finally, once we have filled this cell, that will give us the answer and we will just return the

74
00:05:12,310 --> 00:05:16,240
value that we fill in this cell, whether it's true or false.

75
00:05:16,240 --> 00:05:20,350
So this is the first approach with which we are going to solve this question.

76
00:05:20,350 --> 00:05:24,700
And notice that this is a tabulation approach or bottom up approach.