Question regarding Count palindromes (Practice Easy)

general
, , ,
1

Count Palindromes

Each palindrome can be always created
from the other palindromes, if a
single character is also a palindrome.
For example, the string “bobseesanna”
can be created by some ways:

  • bobseesanna = bob + sees + anna
  • bobseesanna = bob + s + ee + s + anna
  • bobseesanna = b + o + b + sees + a + n + n + a …

We want to take the value of function CountPal(s) which is
the number of different ways to use
the palindromes to create the string s
by the above method. Input

The string s Output

The value of function CountPal(s),
taking the modulo of 1 000 000 007
(109+7)

Limitations

0 < |s| <= 1000 Example

Input: bobseesanna

Output: 18

I’ve been struggling through this problem for quite a few days. I know it must be DP but somehow I couldn’t find a way to formalize the recursive formula. The only thing I have so far is for the base case, when the length of the string is 1, then there is only one way. Could anyone help me understand this problem? I really don’t want to look at the solution because by doing that I won’t learn anything. Any suggestion or idea would be greatly appreciated.

2 Likes
2

What you think about this idea (first thought)?

Find all the palindromes that start at position 0. For each such palindrome ending at position x find

CountPal( s.substring(x+1) )
2 Likes
3

this is a very tough problem sorry i cant solve that problem.

4

Thanks. I will try out this idea.