1
00:00:00,110 --> 00:00:01,070
Welcome back.

2
00:00:01,070 --> 00:00:06,710
In the previous video we have discussed the recursive as well as the memoization approach for solving

3
00:00:06,710 --> 00:00:10,940
this question, and we are discussing the second approach for solving this question.

4
00:00:10,940 --> 00:00:17,510
Now let's go ahead and write the pseudocode so that it becomes very clear how we are going to programmatically

5
00:00:17,510 --> 00:00:19,610
implement the approach that we discussed.

6
00:00:19,610 --> 00:00:22,940
So we will need a recursive function.

7
00:00:22,940 --> 00:00:24,740
Let's just call it check.

8
00:00:24,740 --> 00:00:28,580
And to this function we will be passing an index.

9
00:00:28,580 --> 00:00:30,170
And again that's what we discussed right.

10
00:00:30,170 --> 00:00:33,350
So initially we will be passing this particular index.

11
00:00:33,350 --> 00:00:35,000
That's n minus one.

12
00:00:35,000 --> 00:00:38,600
If n is the length of the string which is given to us okay.

13
00:00:38,600 --> 00:00:41,060
So this is the starting point for this.

14
00:00:41,060 --> 00:00:48,230
And we have also discussed the base case which is that if the index is less than zero then we will just

15
00:00:48,230 --> 00:00:49,190
return true.

16
00:00:49,190 --> 00:00:53,120
And again we have discussed already why we can return true in this case.

17
00:00:53,120 --> 00:00:57,920
So if you are not remembering that please go ahead and take a look at that.

18
00:00:57,920 --> 00:01:01,730
In the previous video where we have discussed the logic for this in detail.

19
00:01:01,730 --> 00:01:03,440
So this is the base case.

20
00:01:03,500 --> 00:01:09,830
Now after the base case before we go ahead and implement the recursive case.

21
00:01:10,440 --> 00:01:18,510
Over here, we will first check whether we have already computed the substring that goes from zero up

22
00:01:18,510 --> 00:01:20,730
to the particular index at hand.

23
00:01:20,730 --> 00:01:27,420
So whether we have already computed whether this particular substring can be formed using words in word

24
00:01:27,420 --> 00:01:28,380
dictionary or not.

25
00:01:28,380 --> 00:01:28,740
Okay.

26
00:01:28,740 --> 00:01:34,710
So for checking whether this was already computed previously or not, we will just check whether depee

27
00:01:34,710 --> 00:01:37,950
at index is not equal to minus one.

28
00:01:37,950 --> 00:01:42,780
Again, initially we will be filling all these cells with the value minus one.

29
00:01:43,390 --> 00:01:51,160
And if we see a case or if we see that DPI index is not minus one, it would mean that we already computed

30
00:01:51,160 --> 00:01:52,750
it and stored it over here.

31
00:01:52,750 --> 00:01:57,040
And that's the reason why DPI index is not equal to minus one.

32
00:01:57,040 --> 00:02:01,210
Now this is the typical thing that we always do for the memoization approach.

33
00:02:01,210 --> 00:02:03,280
So this should be very straightforward.

34
00:02:03,280 --> 00:02:08,830
And if this is not the case then we will go ahead and implement the other things that we discussed.

35
00:02:08,830 --> 00:02:14,800
For the recursive solution we will find whether the substring that starts at index zero and goes up

36
00:02:14,800 --> 00:02:19,810
to the particular index at hand can be formed using words in dictionary or not.

37
00:02:19,810 --> 00:02:28,000
And once we have found that, we will either store true or false at dpi at index and then we will return

38
00:02:28,000 --> 00:02:29,050
true or false.

39
00:02:29,050 --> 00:02:30,700
So that's how we're going to do this.

40
00:02:30,700 --> 00:02:33,220
So over here let's have a for loop.

41
00:02:33,220 --> 00:02:35,710
So for word in word dictionary.

42
00:02:35,710 --> 00:02:39,100
So we're considering every word in the word dictionary.

43
00:02:39,100 --> 00:02:46,990
And we will check whether the substring that starts at index I minus length of the word plus one and

44
00:02:46,990 --> 00:02:48,550
goes up to index I.

45
00:02:48,580 --> 00:02:49,060
Okay.

46
00:02:49,060 --> 00:02:55,060
So that's the first criteria over here whether this particular substring is in the word dictionary okay.

47
00:02:55,060 --> 00:03:01,420
And if it is in the word dictionary we will check whether the remaining part in the substring can be

48
00:03:01,420 --> 00:03:03,430
formed using words in word dictionary.

49
00:03:03,430 --> 00:03:08,020
And for that we are recursively calling the check function again over here and over here.

50
00:03:08,020 --> 00:03:10,030
The index that we will be passing to.

51
00:03:10,030 --> 00:03:16,540
This would be the index which is previous to this particular index, which is the starting index of

52
00:03:16,540 --> 00:03:18,400
this substring that we are considering.

53
00:03:18,400 --> 00:03:22,810
So over here we will be passing the index I minus length of the word.

54
00:03:22,810 --> 00:03:26,350
Notice we have I minus length of the word plus one over here.

55
00:03:26,350 --> 00:03:30,760
And if you subtract one from this you will get I minus length of the word.

56
00:03:30,760 --> 00:03:35,350
And again we have discussed this in detail in the approach video which is the previous video.

57
00:03:35,350 --> 00:03:43,270
And so if this particular substring is a word in word dictionary, and if the previous part of the substring

58
00:03:43,270 --> 00:03:50,710
that we are considering which is zero to index can also be formed using words in word dictionary, then

59
00:03:50,710 --> 00:03:54,640
we will just store and return true okay.

60
00:03:54,640 --> 00:03:58,420
So store means we will say dp at index is true.

61
00:03:58,420 --> 00:04:01,090
And then we will just return dp at index.

62
00:04:01,090 --> 00:04:07,810
And if we were not able to return true over here, after we have gone through every word in word dictionary,

63
00:04:07,810 --> 00:04:12,550
we will come to this line of code where we will just return false.

64
00:04:12,550 --> 00:04:18,730
Okay, because we were not able to return true, which means that we are not able to form the substring

65
00:04:18,730 --> 00:04:24,220
that we are considering, which goes from index zero up to the index at hand, which is this index over

66
00:04:24,220 --> 00:04:24,520
here.

67
00:04:24,520 --> 00:04:31,210
So it means that we were not able to form that particular substring only using words from word dictionary.

68
00:04:31,210 --> 00:04:36,160
So this is the pseudocode for the memoization approach for solving this question.