leetcode 647. 回文子串

题目描述

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

示例 1:
输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.

示例 2:
输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

注意:

  1. 输入的字符串长度不会超过1000。

题解

遍历字符串s,分为奇偶两种情况,例如,xax中的a是回文子串,则xax也是回文子串;xaax中的aa是回文子串,则xaax也是回文子串

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func countSubstrings(s string) int {
length, res := len(s), 0
for i := 0; i < length; i++ {
for j := 0; i-j >= 0 && i+j < length; j++ {
if s[i+j] == s[i-j] {
res++
} else {
break
}
}
for j := 0; i-j >= 0 && i+j+1 < length; j++ {
if s[i+j+1] == s[i-j] {
res++
} else {
break
}
}
}
return res
}