当前位置:网站首页>最长回文子串
最长回文子串
2022-08-09 10:51:00 【ase2014】
题目
最长回文子串
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
说明
- 使用动态规划法,状态转移
- 使用左右index left, right进行探测,检查s[left, right]是否为回文串,则需要判断s[left+1, right-1]为回文串,如果s[left+1, right-1]为回文串,则只要s[left] == s[right]即可
- 如何判断s[left+1, right-1]为回文串,使用逆序进行操作即可,即先判断s[left+1, right-1],记录到flag二维数组里面
以s="babad"为例子,横为i,纵向为j,使用二维数组存储状态,只用一半存储,然后通过二维数组进行状态转移
i:j | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | T | F | T | F | F |
1 | T | F | T | F | |
2 | T | F | F | ||
3 | T | F | |||
4 | T |
代码
func longestPalindrome(s string) string {
sLen := len(s)
if sLen < 2 {
return s
}
flag := make([][]bool, sLen)
for i := 0; i < sLen; i++ {
flag[i] = make([]bool, sLen)
}
result := ""
for i := sLen - 1; i >= 0; i-- {
for j := i; j < sLen; j++ {
// i == j , 如果j-i 小于2,则表明只有两个,两个相等,是回文
// 如果j-i大于2,则只需要判断i+1,j-1是否为回文,如果是,则记录i,j为回文,并判断是否比当前值长
if s[i] == s[j] && (j-i < 2 || flag[i+1][j-1]) {
flag[i][j] = true
tmp := j - i + 1
if len(result) <= tmp {
result = s[i : j+1]
}
}
}
}
return result
}
边栏推荐
猜你喜欢
性能测试(03)-JDBC Request
OneNote 教程,如何在 OneNote 中搜索和查找笔记?
信息系统项目的十大管理
centos7.5 设置Mysql开机自启动
性能测试(01)-jmeter元件-线程组、调试取样器
Preparation for gold three silver four: how to successfully get an Ali offer (experience + interview questions + how to prepare)
c语言函数的递归调用(汉诺塔问题,楼梯递归问题等)
Error: Cannot find module ‘./application‘
ThreadLocal及其内存泄露分析
可能95%的人还在犯的PyTorch错误
随机推荐
electron 应用开发优秀实践
985毕业,工作3年,分享从阿里辞职到了国企的一路辛酸和经验
获取指定年度所有周的工具类
prometheus接入mysqld_exporter
PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization论文阅读
unix环境编程 第十五章 15.3 函数popen和pclose
关于anaconda中conda下载包或者pip下载包很慢的原因,加速下载包的方法(无视anaconda版本和环境)
【原创】JPA中@PrePersist和@PreUpdate的用法
[华为云在线课程][SQL语法分类][数据操作][学习笔记]
PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization Paper Reading
shell脚本实战(第2版)/人民邮电出版社 脚本2 验证输入:仅限字母和数字
unix环境编程 第十五章 15.9 共享存储
依赖注入(Dependency Injection)框架是如何实现的
LM小型可编程控制器软件(基于CoDeSys)笔记二十六:plc的数据存储区(模拟量输入通道部分)
Tensorflow realize parameter adjustment of linear equations
自从我使用HiFlow场景连接器后,在也不用担心成为“落汤鸡”了
1005 Spell It Right (20分)
AQS同步组件-FutureTask解析和用例
json库的dumps()方法和loads()方法
15.8 the semaphore Unix environment programming chapter 15