剑指 Offer II 020. 回文子字符串的个数_回文子字符串个数

题目链接

力扣

题目描述

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

解题思路

回文字符串中的字符数有奇数个和偶数个之分，对于字符串，每个单个字符都是回文子串。

维护两个指针left和right，分别有如下两种情况：

两指针指向同一个字符，分别向左向右移动，每移动一次比较是否相等，相等则+1

两指针指向相邻字符，分别向左向右移动，每移动一次比较是否相等，相等则+1

代码

Python

def countSubstrings(s: str) -> int:
    def countPalindrome(s: str, left: int, right: int, n: int) -> int:
        res = 0
        while left >= 0 and right < n:
            if s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
            else:
                break
        return res
 
    n = len(s)
    ans = 0
    for i in range(n):
        ans += countPalindrome(s, i, i, n) + countPalindrome(s, i, i + 1, n)
    return ans

Go

func countSubstrings(s string) int {
	n := len(s)
	if n <= 1 {
		return n
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans += isPalindrome(s, i, i, n) + isPalindrome(s, i, i+1, n)
	}
	return ans
}
 
func isPalindrome(s string, left int, right int, n int) int {
	res := 0
	for {
		if left < 0 || right > n-1 {
			break
		}
		if s[left] == s[right] {
			res++
			left--
			right++
		} else {
			break
		}
	}
	return res
}