高效判断回文子串技巧

今天学习到一个新的技巧来快速判断回文子串：该方法是通过中心扩展来高效判断是否是回文字符串。回文字符串分为奇回文和偶回文，其中奇回文的中心只有一个，偶回文的中心有两个，所以通过遍历中心来左右扩展判断回文字符串。假设字符串的长度为n，那么如果是奇回文，中心个数就是n个；如果是偶回文，中心个数就是n - 1个，那么总共需要遍历的中心个数就是2n - 1个。其中每次遍历中心的left，right分别是i / 2，i / 2 + i mod 2，如果是回文字符串就left--, right++的往左右两边扩散。此方法的时间复杂度是O(N²)，因为枚举每个中心需要O(N)的复杂度，每个中心扩展又需要O（N）的复杂度，所以总的时间复杂度是O（N²）

具体代码如下：

func countSubstrings(s string) int {
	n := len(s)
	res := 0
	for i := 0; i < 2 * n - 1; i++ {
		l, r := i / 2, i / 2 + i % 2
		for l >= 0 && r < n && s[l] == s[r] {
			res++
			l--
			r++
		}
	}
	return res
}