2021-12-22:回文子串。 给你一个字符串 s ,请你统计并返
2023-04-18 16:09:03 时间
2021-12-22:回文子串。
给你一个字符串 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。
答案2021-12-22:
马拉车算法。每个中心求个数然后求和。
时间复杂度:O(n)。
空间复杂度:O(n)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
s := "moonfdd"
ret := countSubstrings(s)
fmt.Println(ret)
}
func countSubstrings(s string) int {
if len(s) == 0 {
return 0
}
dp := getManacherDP(s)
ans := 0
for i := 0; i < len(dp); i++ {
ans += dp[i] >> 1
}
return ans
}
func getManacherDP(s string) []int {
str := manacherString(s)
pArr := make([]int, len(str))
C := -1
R := -1
for i := 0; i < len(str); i++ {
if R > i {
pArr[i] = getMin(pArr[2*C-i], R-i)
} else {
pArr[i] = 1
}
for i+pArr[i] < len(str) && i-pArr[i] > -1 {
if str[i+pArr[i]] == str[i-pArr[i]] {
pArr[i]++
} else {
break
}
}
if i+pArr[i] > R {
R = i + pArr[i]
C = i
}
}
return pArr
}
func manacherString(str string) []byte {
charArr := []byte(str)
res := make([]byte, len(str)*2+1)
index := 0
for i := 0; i != len(res); i++ {
if i&1 == 0 {
res[i] = '#'
} else {
res[i] = charArr[index]
index++
}
}
return res
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下:
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击