Problem : The number of ways one could remove letters from a particular word so that it would become a palindrome.Two ways that differ due to order of removing letters are considered the same. And it can also be the case that no letters have to be removed to form a palindrome.
I am trying to solve this problem . But my solution gives wrong answer . Then I found a solution that works here. But don't understand the recurrence . Something like this ..
ll rec(int i, int j)
{
if(j < i) return 0;
if(i == j) return 1;
ll &ret = dp[i][j];
if(ret != -1) return ret;
if(str[i] == str[j])
return ret = 1 + rec(i+1, j) + rec(i, j-1);
else
return ret = rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1);
}
I don't understand why subtract rec(i+1, j-1) ? For order of removing letters are considered the same, means we count same way 2 times that why subtract ? Please explain the recurrence , thanks in advance .
I think this way is better for understanding:
rec(i+1, j) means you remove ith character and rec(i, j+1) means you remove jth character. In both rec(i+1, j) and rec(i, j-1) you will call rec(i+1, j-1). So you count rec(i+1, j-1) twice if you don't subtract it.
Thanks for your great help. Now I understand .
In the first return case why do we calculate rec(i+1 , j-1) ?? Since as described it will be generated by rec(i+1, j) and rec(i, j-)...
Please explain...
let the string from i to j is AAAA, i=0, j=3 . if(condition) is executed.. => char A at i=0, and char A at j=3, form palindrom so +1, => rec(i+1, j-1), calculate any palindrom that can be concatenated with above palindrom... => rec(i+1, j) + rec(i, j-1) — rec(i+1, j-1), calculate same palindroms as in 2nd step but this time not concetenate with palindrom in 1st step. Hope i am right....
I'm still confused on the recurrence relation here,can you be more specific please? :(
I hope this explanation makes the solution clear to you. If there is just one character in the string, it's a palindrome. If there are more characters left in the string, you can remove character from left
rec(i+1, j)
or rightrec(i, j-1)
. But in both recursions you will countrec(i+1, j-1)
. To avoid counting twice, we subtract it from ret. There is only one case left: whenstr[i] == str[j]
, you can keep both characters (do not remove them) and then you should call rec(i+1, j-1) to build the middle and we add one because we never count the palindrome consisting of just these two characters.