LCR 020. 回文子串(中等)(主站647)

https://leetcode.cn/problems/a7VOhD/
https://leetcode.cn/problems/palindromic-substrings/
难度：☆☆☆

题目：

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例：

输入：s = “abc”
输出：3

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

方法1：字符串，暴力遍历

Python
时间复杂度：O(N^{3)。
空间复杂度：O(n)。}

class Solution:
    def countSubstrings(self, s: str) -> int:
        cnt = 0
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                if s[i:j] == s[i:j][::-1]:
                    cnt += 1
        return cnt

Java
时间复杂度：O(N³)。
空间复杂度：O(n²)。

class Solution {
    public int countSubstrings(String s) {
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length() + 1; j++) {
                if (s.substring(i, j).toString().contentEquals(new StringBuilder(s.substring(i, j)).reverse())) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

方法2：字符串，逆向双指针+中心扩展

先定好一个位置，然后向两端扩展，左右字符相等一次即是一个回文字符串，相等一次就加1。
注意回文有单中心和双中心2种情况。
Python
时间复杂度：O(N²)。
空间复杂度:O(1)。

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i in range(n):
            ans += self.isPalindrome(s, i, i)
            ans += self.isPalindrome(s, i, i + 1)
        return ans
    
    def isPalindrome(self, ss, left, right):
        nn = len(ss)
        cnt = 0
        while left >=0 and right < nn and ss[left] == ss[right]:
            cnt += 1
            left -= 1
            right += 1
        return cnt

Java
时间复杂度：O(N²)。
空间复杂度:O(1)

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            ans += isPalindrome(s, i, i);
            ans += isPalindrome(s, i, i + 1);
        }
        return ans;
    }
    public int isPalindrome(String ss, int left, int right) {
        int cnt = 0;
        while (left >= 0 && right < ss.length() && ss.charAt(left) == ss.charAt(right)) {
            cnt++;
            left--;
            right++;
        }
        return cnt;
    }
}