1
00:00:00,760 --> 00:00:02,650
Hey there and welcome back!

2
00:00:02,830 --> 00:00:08,590
In this video, let's take a look at the recursion tree of the approach that we have so far discussed

3
00:00:08,590 --> 00:00:11,290
for solving the palindrome substrings question.

4
00:00:11,320 --> 00:00:14,110
So let's say this is the string that is given to us.

5
00:00:14,140 --> 00:00:21,280
Notice that the last valid index is equal to five and the first valid index is equal to zero.

6
00:00:21,310 --> 00:00:24,610
Now we have already written the ace palindrome function.

7
00:00:24,610 --> 00:00:28,660
So first we will be passing zero and five to this function.

8
00:00:29,170 --> 00:00:36,310
And inside the body of this function we would make a call to the same function recursively passing zero

9
00:00:36,310 --> 00:00:38,500
and four and one and five.

10
00:00:38,500 --> 00:00:43,420
So again notice that over here we are only moving one pointer at a time.

11
00:00:43,420 --> 00:00:48,130
And then we will also be checking whether p over here is equal to s.

12
00:00:48,130 --> 00:00:51,280
And we see that these two characters are not equal.

13
00:00:51,280 --> 00:00:58,750
And therefore the string that starts at index zero and goes up to index five is not a palindrome.

14
00:00:58,750 --> 00:01:05,140
And this problem over here is represented at this cell in the DP table.

15
00:01:05,140 --> 00:01:08,050
Because notice the start index over here is zero.

16
00:01:08,050 --> 00:01:10,600
And the end index is equal to five.

17
00:01:10,600 --> 00:01:15,820
So the string represented by this cell over here is not a palindrome.

18
00:01:15,820 --> 00:01:18,400
And we can fill false over here.

19
00:01:18,700 --> 00:01:19,810
Let's continue.

20
00:01:19,810 --> 00:01:28,150
Now the call over here to the same recursive function which passes the indices zero and four will make

21
00:01:28,150 --> 00:01:29,860
again recursive calls.

22
00:01:29,860 --> 00:01:36,280
And the indices that would be passed to the same function at those instances will be zero comma three,

23
00:01:36,280 --> 00:01:37,630
one comma four.

24
00:01:37,630 --> 00:01:43,420
And then we would also check whether this string over here, which starts at index zero and goes up

25
00:01:43,420 --> 00:01:46,120
to index four, is a palindrome or not.

26
00:01:46,120 --> 00:01:50,710
Again, in these two cases we are only moving one pointer at a time.

27
00:01:50,710 --> 00:01:55,090
And over here when we check the characters at index zero and four.

28
00:01:55,830 --> 00:01:57,930
We see that these two are equal.

29
00:01:57,930 --> 00:02:02,580
And again, the string that we are considering is not of length two.

30
00:02:02,610 --> 00:02:09,600
So we would check the substring that starts at index one and goes up to three to identify whether the

31
00:02:09,600 --> 00:02:13,860
whole substring over here which is being considered is a palindrome or not.

32
00:02:13,890 --> 00:02:19,650
Now when we do this check that goes from 1 to 3, we see that this is not a palindrome.

33
00:02:19,650 --> 00:02:21,390
So this would return false.

34
00:02:21,390 --> 00:02:27,120
And therefore we know that the string that goes from zero up to four is not a palindrome.

35
00:02:27,120 --> 00:02:30,600
And that's represented by this cell in the DP table.

36
00:02:30,600 --> 00:02:32,610
And we fill false over here.

37
00:02:32,610 --> 00:02:36,930
So you can see that the way that this proceeds is pretty straightforward.

38
00:02:36,930 --> 00:02:44,520
And in this way we would be able to fill the DP table over here with either true or false true indicating

39
00:02:44,520 --> 00:02:50,610
that the substring at hand is a palindrome, and false, indicating that the substring at hand is not

40
00:02:50,610 --> 00:02:51,510
a palindrome.