前言：
而今看官们对“manacher算法时间复杂度”都比较讲究，大家都想要学习一些“manacher算法时间复杂度”的相关资讯。那么小编也在网上收集了一些关于“manacher算法时间复杂度””的相关文章，希望大家能喜欢，各位老铁们一起来了解一下吧！题目
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：输入：s = "abc" 输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：输入：s = "aaa" 输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：1 <= s.length <= 1000
s 由小写英文字母组成
注意：本题与主站 647 题相同：
解题思路分析
1、中心扩展；时间复杂度O(n^2)，空间复杂度O(1)
func countSubstrings(s string) int { n := len(s) res := 0 for i := 0; i < 2*n-1; i++ { left, right := i/2, i/2+i%2 for ; 0 <= left && right < n && s[left] == s[right]; left, right = left-1, right+1 { res++ } } return res}2、Manacher算法；时间复杂度O(n^2)，空间复杂度O(1)
func countSubstrings(s string) int { if len(s) <= 1 { return len(s) } str := add(s) length := len(str) res := 0 for i := 0; i < length; i++ { curLength := search(str, i) res = res + curLength/2 + curLength%2 } return res}func add(s string) string { var res []rune for _, v := range s { res = append(res, '#') res = append(res, v) } res = append(res, '#') return string(res)}func search(s string, center int) int { i := center - 1 j := center + 1 step := 0 for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 { step++ } return step}3、Manacher算法；时间复杂度O(n)，空间复杂度O(n)
func countSubstrings(s string) int { var res []rune res = append(res, '$') for _, v := range s { res = append(res, '#') res = append(res, v) } res = append(res, '#') res = append(res, '!') str := string(res) n := len(str) - 1 arr := make([]int, n) leftMax, rightMax, result := 0, 0, 0 for i := 1; i < n; i++ { if i <= rightMax { arr[i] = min(rightMax-i+1, arr[2*leftMax-i]) } else { arr[i] = 1 } for str[i+arr[i]] == str[i-arr[i]] { arr[i]++ } if i+arr[i]-1 > rightMax { leftMax = i rightMax = i + arr[i] - 1 } result = result + arr[i]/2 } return result}func min(a, b int) int { if a > b { return b } return a}4、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)
func countSubstrings(s string) int { if len(s) <= 1 { return len(s) } dp := make([][]bool, len(s)) res := 0 for r := 0; r < len(s); r++ { dp[r] = make([]bool, len(s)) dp[r][r] = true res++ for l := 0; l < r; l++ { if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) { dp[l][r] = true } else { dp[l][r] = false } if dp[l][r] == true { res++ } } } return res}5、暴力法；时间复杂度O(n^3)，空间复杂度O(1)
func countSubstrings(s string) int { if len(s) <= 1 { return len(s) } res := len(s) for i := 0; i < len(s)-1; i++ { for j := i + 1; j < len(s); j++ { if s[i] == s[j] && judge(s, i, j) == true { res++ } } } return res}func judge(s string, i, j int) bool { for i <= j { if s[i] != s[j] { return false } i++ j-- } return true}总结Medium题目，题目同leetcode 647.回文子串，类似的题目还有 leetcode 5.最长回文子串
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
