最长回文子串 (动态规划法、中心扩展算法)

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/ (多解法)

描述

给定一个字符串 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;
}

最新文章

  1. [转]Java中Map的用法详解
  2. opengl中拾取操作的实现
  3. 【jQuery UI 1.8 The User Interface Library for jQuery】.学习笔记.7.Slider控件
  4. JPA--联合主键
  5. php专业面试总结
  6. USACO Section 1.1 Greedy Gift Givers 解题报告
  7. td文字过长部分显示,鼠标移动显示全部内容
  8. 【DDD】领域驱动设计实践 —— 架构风格及架构实例
  9. mysql单独可连接,php连接mysql失败之 Can&#39;t connect to local MySQL server through socket &#39;/var/lib/mysql/mysql.sock&#39; (2)
  10. droid invalidate和postinvalidate的区别
  11. java多继承
  12. 用dockerfile创建jmeter的docker镜像
  13. MQ选型之RabbitMQ
  14. 验证代理ip是否可用
  15. QT和MFC的差别
  16. Innodb semi-consistent 简介
  17. unity3d 第一人称脚本解释MouseLook
  18. Jenkins+Jmeter+Ant自动化集成及邮件正文以html输出
  19. Java数据库连接池原理与简易实现
  20. bat设置windows计划任务

热门文章

  1. Python 初级 6 循环 (二)
  2. [Bayes] Concept Search and LDA
  3. 【翻译】Flink Table Api &amp; SQL — Hive Beta
  4. cmake find_package说明
  5. [LeetCode] 47. Permutations II 全排列 II
  6. jmap使用
  7. vscode插件Power Mode
  8. Postgresql集群解决方案测试报告
  9. springboot2 配置 https
  10. java注解简单使用