1
00:00:00,470 --> 00:00:01,490
Welcome back.

2
00:00:01,490 --> 00:00:08,090
In the previous videos we have discussed the memoization approach for solving the palindromic substrings

3
00:00:08,090 --> 00:00:09,620
question over here.

4
00:00:09,620 --> 00:00:13,940
Let's go ahead and write the pseudocode for the approach that we have discussed.

5
00:00:13,940 --> 00:00:21,170
So because the memoization approach is a recursive approach, we would need to think of the base case

6
00:00:21,170 --> 00:00:25,220
as well as the recursive case of the approach that we come up with.

7
00:00:25,220 --> 00:00:28,010
So let's go ahead and make some space over here.

8
00:00:28,010 --> 00:00:33,680
And let's call the function that we are going to write over here as is palindrome.

9
00:00:33,680 --> 00:00:38,030
And to this function we would have to pass two variables.

10
00:00:38,030 --> 00:00:40,820
And over here I've just called them I and j.

11
00:00:40,820 --> 00:00:45,620
So I is the starting index and j is the ending index.

12
00:00:45,620 --> 00:00:52,280
So by just having a combination of these two values we would be able to determine the substring that

13
00:00:52,280 --> 00:00:53,360
we are evaluating.

14
00:00:53,360 --> 00:00:59,240
So for example if I is zero and j is five we are evaluating the whole string.

15
00:00:59,240 --> 00:01:06,860
And let's say if I is equal to two and j is equal to four, then we are evaluating prpp which is a substring.

16
00:01:06,860 --> 00:01:09,890
And then we would be calling this function for the first time.

17
00:01:09,890 --> 00:01:12,020
And over here we are passing zero.

18
00:01:12,020 --> 00:01:17,600
And the last valid index which is length of the string given to us minus one.

19
00:01:17,600 --> 00:01:23,090
And then over here recursively we will be visiting all the possible substrings.

20
00:01:23,090 --> 00:01:32,360
And for each substring we will either populate true or false to the cell in the DP table over here which

21
00:01:32,360 --> 00:01:34,910
represents that particular substring.

22
00:01:34,910 --> 00:01:38,840
So this is the memoization approach for solving this question.

23
00:01:38,840 --> 00:01:46,580
Now we have already discussed the recursive case which is to first check whether the substring that

24
00:01:46,580 --> 00:01:51,590
starts at I plus one and goes up to j is a palindrome or not.

25
00:01:51,590 --> 00:01:57,500
We would also have to check the substring that starts at I and goes up to j minus one.

26
00:01:57,500 --> 00:02:02,270
So these are the two recursive calls to check these two scenarios.

27
00:02:02,270 --> 00:02:05,270
And we have discussed previously why this is required.

28
00:02:05,270 --> 00:02:11,300
So we are just moving one pointer among I and J at a time in these two calls.

29
00:02:11,300 --> 00:02:18,950
And then we would also need to check whether the substring that starts at I and goes up to j is a palindrome

30
00:02:18,950 --> 00:02:19,520
or not.

31
00:02:19,520 --> 00:02:25,310
So for this we would have to compare the characters at indices I and j respectively.

32
00:02:25,310 --> 00:02:33,140
So if these two are equal, then we would need to check whether either we are just dealing with a substring

33
00:02:33,140 --> 00:02:40,610
that is of length two, or whether the substring that starts at I plus one and goes up to j minus one

34
00:02:40,610 --> 00:02:42,380
is a palindrome or not.

35
00:02:42,380 --> 00:02:49,880
So if this is true, and if either of these is true, then we know that the string or the substring

36
00:02:49,880 --> 00:02:53,900
that starts at index I and goes up to j is a palindrome.

37
00:02:53,900 --> 00:03:00,890
And we would fill true in the cell over here in the DP table that represents that particular substring.

38
00:03:00,890 --> 00:03:05,900
So this is the recursive case for solving the palindrome substring question.

39
00:03:05,900 --> 00:03:08,780
Now let's also think of the base case.

40
00:03:08,780 --> 00:03:13,940
Now again we have discussed that this function over here will go through all the possible substrings

41
00:03:13,940 --> 00:03:21,230
and fill either true or false in the respective places in the DP table, which represents the substring

42
00:03:21,230 --> 00:03:21,800
at hand.

43
00:03:21,830 --> 00:03:28,520
Now, when it comes to the base case, we just need to check whether I is equal to j, because in that

44
00:03:28,520 --> 00:03:33,770
case we are dealing with a substring of length one and we can just return true.

45
00:03:33,770 --> 00:03:36,860
And you will also see that in some solutions.

46
00:03:36,860 --> 00:03:44,750
The base case also has this check that if j is less than I, or if the ending index is less than the

47
00:03:44,750 --> 00:03:47,840
starting index, we can just return false.

48
00:03:47,840 --> 00:03:53,510
Now you can go ahead and write this, but this is not required because notice that over here we have

49
00:03:53,510 --> 00:03:58,400
a separate check to check whether the string at hand just has two characters.

50
00:03:58,400 --> 00:04:05,060
So because we would get true over here for that we would not execute this recursive call where we just

51
00:04:05,060 --> 00:04:05,960
have two characters.

52
00:04:05,960 --> 00:04:13,910
So for example, if I is pointing to index zero and j is pointing to index one, then we would not call

53
00:04:13,910 --> 00:04:19,820
the recursive function over here with I plus one j minus one, which would cause this type of a scenario

54
00:04:19,820 --> 00:04:24,440
because over here first we are checking whether j is equal to I plus one.

55
00:04:24,440 --> 00:04:27,380
So because of this we do not need this check.

56
00:04:27,380 --> 00:04:32,750
But if you reverse this, if you write this first and then you write this over here, when you write

57
00:04:32,750 --> 00:04:35,930
the condition to check whether this is a palindrome or not.

58
00:04:35,930 --> 00:04:41,330
So if you write this first and then you write this, then you would need to add this as well to the

59
00:04:41,330 --> 00:04:41,990
base case.

60
00:04:41,990 --> 00:04:45,230
So we have discussed the base case and the recursive case.

61
00:04:45,230 --> 00:04:51,440
And we are done writing the pseudo code for the memoization approach for solving the palindrome substrings

62
00:04:51,440 --> 00:04:52,070
question.