r*****t
发帖数: 68 | 1 Q: Find the number of substrings of a string that are palindromes.
Can it be solved by O(n)?
My idea is to build an array p[i,j]=1 if string(i,...j) is palindrome
otherwise p[i,j]=0. Then sum of p[i,j] is the total number. This is a DP
idea by O(n^2).
Better solution? Thanks. | f*****e
发帖数: 2992 | 2 看起来stack可能有用。
【在 r*****t 的大作中提到】
: Q: Find the number of substrings of a string that are palindromes.
: Can it be solved by O(n)?
: My idea is to build an array p[i,j]=1 if string(i,...j) is palindrome
: otherwise p[i,j]=0. Then sum of p[i,j] is the total number. This is a DP
: idea by O(n^2).
: Better solution? Thanks.
| r*****e
发帖数: 792 | 3 my first instinct is to use Manacher's Algorithm which finds the longest
palindrome in linear time. But not sure if it can be applied to solve
this problem where multiple palindromes need to be found.
【在 r*****t 的大作中提到】
: Q: Find the number of substrings of a string that are palindromes.
: Can it be solved by O(n)?
: My idea is to build an array p[i,j]=1 if string(i,...j) is palindrome
: otherwise p[i,j]=0. Then sum of p[i,j] is the total number. This is a DP
: idea by O(n^2).
: Better solution? Thanks.
|
|
