[LeetCode] 5. 最长回文子串 ☆☆☆(最长子串、动态规划)
2024-08-21 13:35:40
描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
解析
将字符串倒序,然后对比形同的序列。----两字符串的公共子串。
字符串中的每个字符,向两边发散比较。注意有偶数子串、奇数子串。
代码(还有其他解法)
中心扩展算法
public String longestPalindrome_reconstructure2(String s) { // 第二次对代码进行重构
if (s.length() < 2) { // 单个字符肯定是回文串,直接返回s
return s;
}
int maxLength = 0;
int center = 0;
for (int i = 0; i < s.length(); i++){
int begin = centerExpand(s, i, i); // 最长回文串长度为奇数
int end = centerExpand(s, i, i + 1); // 最长回文串长度为偶数 if (maxLength < Math.max(begin, end)){
center = i; // 以center为中心
maxLength = Math.max(begin, end); // 最长回文串长度
}
}
//如ababaabc,最后center为2,maxLength为5
// 如果我们的回文串的长度为偶数,那么中心左边的长度会比右边的长度小1
return s.substring(center - (maxLength - 1) / 2, center + maxLength / 2 + 1);
} int centerExpand(String s, int begin, int end){
int left = begin, right = end;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
// 返回以begin,end为基准,同时向左向右扩展后能够得到的最长回文串长度(最后left较正确子串的值小1,right大1,所以这里减1。另一个1,由于下标的原因)
return right - left - 1;
}
最新文章
- [转]Java中Map的用法详解
- opengl中拾取操作的实现
- 【jQuery UI 1.8 The User Interface Library for jQuery】.学习笔记.7.Slider控件
- JPA--联合主键
- php专业面试总结
- USACO Section 1.1 Greedy Gift Givers 解题报告
- td文字过长部分显示,鼠标移动显示全部内容
- 【DDD】领域驱动设计实践 —— 架构风格及架构实例
- mysql单独可连接,php连接mysql失败之 Can&#39;t connect to local MySQL server through socket &#39;/var/lib/mysql/mysql.sock&#39; (2)
- droid invalidate和postinvalidate的区别
- java多继承
- 用dockerfile创建jmeter的docker镜像
- MQ选型之RabbitMQ
- 验证代理ip是否可用
- QT和MFC的差别
- Innodb semi-consistent 简介
- unity3d 第一人称脚本解释MouseLook
- Jenkins+Jmeter+Ant自动化集成及邮件正文以html输出
- Java数据库连接池原理与简易实现
- bat设置windows计划任务