[刷题防痴呆] 0647 - 回文子串 (Palindromic

题目地址

https://leetcode.com/problems/palindromic-substrings/

题目描述

647. Palindromic Substrings


Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

思路

• 基于中心点枚举的算法.
• 从中间往两边.
• 关键是走两遍.
• 左右不是同一个, 和左右是同一个.

关键点

代码

• 语言支持：Java

class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += find(s, i, i);
            count += find(s, i, i + 1);
        }

        return count;
    }

    private int find(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            count++;
            left--;
            right++;
        }

        return count;
    }
}