1
00:00:00,770 --> 00:00:01,940
Welcome back.

2
00:00:01,940 --> 00:00:09,650
In the next few videos, we will be discussing the memoization and tabulation approach for solving the

3
00:00:09,650 --> 00:00:11,480
palindromic substrings question.

4
00:00:11,480 --> 00:00:14,870
So let's get started with the memoization approach.

5
00:00:14,870 --> 00:00:21,980
So let's say the string that is given to us is p q p r p s.

6
00:00:21,980 --> 00:00:22,610
Okay.

7
00:00:22,610 --> 00:00:25,310
So let's say this is the string that is given to us.

8
00:00:25,310 --> 00:00:28,790
Now how would the memoization table look like?

9
00:00:28,790 --> 00:00:35,240
We would need a table that can represent all the possible substrings that can be formed.

10
00:00:35,240 --> 00:00:44,240
So that is why we will have p q p r p s on the columns to indicate each of these characters, as well

11
00:00:44,240 --> 00:00:47,600
as rows to indicate each of these characters.

12
00:00:47,600 --> 00:00:50,990
So the DP table would look something like this over here.

13
00:00:50,990 --> 00:00:53,660
So let's write the indices over here.

14
00:00:53,660 --> 00:00:56,330
That's 012345.

15
00:00:56,330 --> 00:01:03,290
So you can see that we have one column for each of these indices and one row for each of these indices.

16
00:01:03,290 --> 00:01:08,870
So if this is the DP table that we will be using what does each cell represent.

17
00:01:08,870 --> 00:01:12,830
For example what does this cell over here represent.

18
00:01:12,830 --> 00:01:19,760
So this cell over here notice has one as the row and three as the column.

19
00:01:19,760 --> 00:01:27,440
So this cell represents the substring that starts with the character at index one and goes up to the

20
00:01:27,440 --> 00:01:32,300
character at index three which is q p and r.

21
00:01:32,630 --> 00:01:37,460
So in this way the row value gives us the starting index.

22
00:01:37,460 --> 00:01:41,090
And the column value gives us the ending index.

23
00:01:41,090 --> 00:01:49,250
And in this manner we will be able to represent all the possible substrings using this DP table over

24
00:01:49,250 --> 00:01:49,640
here.

25
00:01:49,640 --> 00:01:56,840
And then once we find that a substring is a palindrome, we will store the value true in that particular

26
00:01:56,840 --> 00:01:57,200
cell.

27
00:01:57,200 --> 00:02:03,470
And on the other hand, if we find that a substring is not a palindrome, we will store false in the

28
00:02:03,470 --> 00:02:05,720
cell that represents that substring.

29
00:02:05,720 --> 00:02:10,820
So this is how we will go ahead with the memoization approach for solving this question.

30
00:02:11,030 --> 00:02:17,780
Now let's also discuss how we can use recursion to come up with all the possible substrings.

31
00:02:17,780 --> 00:02:25,430
So initially we would be checking the substring which starts at index zero and goes up to index five.

32
00:02:25,430 --> 00:02:30,050
So this would be inside a function call to a recursive function.

33
00:02:30,350 --> 00:02:36,740
And over here inside the body of the function we would have to check whether this substring over here

34
00:02:36,740 --> 00:02:40,070
that goes from 0 to 5 is a palindrome or not.

35
00:02:40,070 --> 00:02:46,460
If it is, we would store true at the cell that represents this substring in the DP table over here.

36
00:02:46,460 --> 00:02:52,160
And we would also check the substring that goes from 1 to 5.

37
00:02:53,300 --> 00:02:56,060
And from 0 to 4.

38
00:02:56,570 --> 00:03:02,600
Now in these two instances, we are again recursively calling the same function, but we are only moving

39
00:03:02,600 --> 00:03:03,470
one index.

40
00:03:03,470 --> 00:03:08,870
So in this case we have moved 0 to 1, and in this case we have moved 5 to 4.

41
00:03:08,870 --> 00:03:12,410
Again we have discussed in a previous video why this is necessary.

42
00:03:12,410 --> 00:03:19,880
So using this approach we will be able to recursively ensure that we visit all the possible substrings

43
00:03:19,880 --> 00:03:28,730
and either store true or false in the cells in the DP table that represent those respective subproblems.

44
00:03:28,790 --> 00:03:34,130
Now, in the next video, let's go ahead and write the pseudocode for this approach.