题目
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。
示例 1:
1
2
3 输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".示例 2:
1
2
3 输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".注意:
- 输入的字符串长度不会超过1000。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
与最长回文字串一样,用中心拓展法搜索以每个位置为中心的回文字串。仍然需要注意奇数与偶数,且奇数为字符间间隙的前提下,间隙本身不算入总数。
代码:
1 | class Solution { |
错误现象
调试过程中发现一个错误:
1 | r = (i+1) >> 1; // 得到错误结果,i=1时,r=0 |
然而使用MinGW64
编译如下代码:
1 | int i = 1; |
输出为
1 | 1 |
看来是与编译器实现相关的错误,以后对带符号类型使用移位操作时要注意。