高效判断回文子串技巧
原创
今天学习到一个新的技巧来快速判断回文子串：该方法是通过中心扩展来高效判断是否是回文字符串。回文字符串分为奇回文和偶回文，其中奇回文的中心只有一个，偶回文的中心有两个，所以通过遍历中心来左右扩展判断回文字符串。假设字符串的长度为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
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读