【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;
    }
}