【LeetCode】【算法】647. 回文子串

LeetCode 647.回文子串

题目描述

给你一个字符串s，请你统计并返回这个字符串中回文子串的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。

思路

思路：中心拓展法
中心拓展法的意思是说：

1. 假如字符串长度为奇数，从中间的某一位出发，同时向左和向右，能够得到同样的结果，回文子串数量++
2. 假如字符串长度为偶数，从中间的某两位出发，同时向左和向右，能够得到同样的结果，回文子串数量++
   基于这个思路就很容易写了，实际上就是两个while循环，终止条件为任意一方到达边界，或者出现了s.charAt(i) != s.charAt(j)的情况，就结束while循环；否则指针一直移动，回文子串数量一直++

代码

class Solution {public int countSubstrings(String s) {int count = 0;for (int i = 0; i < s.length(); i++) {// 中心拓展法int cur_count = 0;// 向两边拓展// 如果像下面这种写法，就只是以i作为中心了，事实上并不止这一种情况，还有l=i，r=i+1作为回文中心（即回文子串长度为偶数的情况）int l = i;int r = i;while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {cur_count++;l--;r++;}l = i;r = i + 1;while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {cur_count++;l--;r++;}count += cur_count;}return count;}
}