leetcode-5 最长回文子串-画蛇添足的马拉车算法
leetcode-5 最长回文子串
题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd" 输出: "bb"
分析
初步分析
首先能想到的就是暴力解法,遍历每一个字符,寻找以该字符为中心或者以该字符和下一个字符为中心的最大的回文子串,时间复杂度O(n2),具体见下面代码。
第一个问题:暴力解法有哪些地方是可以优化的?
其实要回答这个问题并不简单,有些题目的可优化点是容易看到的,而有些并非轻易看到,比如本题,要回答这个问题还是要从题目给出的线索中寻找。题目说回文串,我们就要充分利用到这个回文串的特性,回文串的特性比较简单(为了简单起见下文先考虑bab这种长度为奇数的回文子串):
假设对称中心为id,x、y是关于id对称的,即x+y=2*id,那么arr[x]=arr[y]
除此之外无其他本质特性了。其他特性就是再根据一些场景和上述本质特性推导出来的特性,这种无非就是利用对称对等关系,利用多组对称对等关系可以得出一些其他结论。例如如下场景:
描述如下:
- arr是字符数组,图中a~g的下标是对应字符在数组中的位置
- a~g是一个关于d对称的回文串,b和f关于d对称,有arr[a]=arr[g]
- a~c是一个关于b对称的回文串,有arr[a]=arr[c]
- e和g关于f对称,我们来推算arr[e]和arr[g]的关系
a和g关于d对称,b和f关于d对称,a和c关于b对称,e和g关于f对称,可以得到c和e关于d对称,由于a~g是一个回文子串,那么就有arr[c]=arr[e]
再根据上述已知条件,得知arr[c]=arr[a]=arr[g],那么arr[e]=arr[g],即e~g也是一个关于f对称的回文串,并且这个回文串跟以b为中心的回文串是一样的。也就可以得到如下推导结论:
- 在一个回文串内,b和f对称,那么以b为对称中心的回文子串和以f为对称中心的回文子串是一模一样的
根据上述推导结论来重新看待上述暴力解法,以上述例子为例,我们在遍历到d后,找到了它的最大回文子串a~g,那么对于求解以d~g之间的字符为中心的回文子串时可以充分利用到他们的对称点的回文子串而不必再从0开始一个一个从对称点开始比较了(仅限包含在a~g大串内部的,因为一旦超出a~g上述推导结论就不能成立了)
利用推导结论进行优化
总结下上述优化的一些关键点:在一个回文串中,可以优化该回文串中右半部分字符的求解过程。所以需要尽量找到一个右临界点最大的回文串,这样就容易将很多字符纳入到优化中。留一个思考点:右临界点最大一定是最优的吗?
前面说的优化有一个大前提,必须在一个回文串内部,仍以上图为例:
以b为中心的最长回文串可能在a~g内部,也可能超出a,我们只能得出在以b为中心的最长回文子串在a~g内部这一部分和以f为中心的最长回文子串在a~g内部这一部分是一模一样的,即可以省去对比过程,但是对于超出a~g的部分是无法判断的,只能按照老办法一个一个去匹配
所以我们需要记录字符b对应的最长回文子串的半长度p,那么减少的判断个数就是min(p,b-a),后续仍要继续匹配,具体来说就是如下代码
int targetId = 0; int targetLen = 0; int maxRight = 0; int id = 0; int[] pLens = new int[newArr.length]; for (int i = 0; i < newArr.length; i++) { pLens[i] = maxRight > i ? Math.min(pLens[2 * id - i], maxRight - i) : 1; int left = i - pLens[i]; int right = i + pLens[i]; while (left >= 0 && right < newArr.length && newArr[left] == newArr[right]) { pLens[i] = pLens[i] + 1; left--; right++; } int newRight = i + pLens[i] - 1; if (newRight > maxRight) { maxRight = newRight; id = i; } if (pLens[i] > targetLen) { targetId = i; targetLen = pLens[i]; } }
总体来说仍然是遍历每个字符,优化就是一旦该字符在最右临界点的回文子串内,可以减少一些判断次数,假如不在最右临界点内,则还是老老实实一个一个匹配。
上述Math.min(pLens[2 * id - i], maxRight - i),前者是最长i的对称点的最长回文子串的长度,maxRight-i则是将回文子串长度局限在了回文子串内,只有这样才能利用推导结论来优化
讨论回文串长度的奇数和偶数
上面优化的思路就是马拉车算法的核心,但是马拉车算法提出需要对每个字符串之间插入特殊字符来规避回文串长度的奇数和偶数的问题,是否真的有必要?
前面为了简化分析,只讨论了回文串长度为奇数的情况,那么对于abba这样的回文串,会对上述分析产生什么样的影响?
对于上述推导结论并不产生实质性的影响,还是以上图为例,b和f关于某个中心对称,那么以f为对称中心的回文串和以b为对称中心的回文串是符合上述推导结论的,并且以f+0.5为对称中心的回文串和以b+0.5为对称中心的回文串仍然是符合上述推导结论的,那就意味着不管回文串的长度是奇数还是偶数,都可以采用上述优化思路来进行优化,完全可以做到一视同仁
只需要在遍历每个字符时,除了要求解以每个字符为对称中心的最长回文串还要求解以每个字符+0.5为对称中心的最长回文串,具体见下面代码。也就是说马拉车算法的预处理其实就是画蛇添足,还额外增加了2N的存储,还额外多遍历了一遍N。同时相比我的方案,还有很多多余的判断比如判断#是否等于#
代码
暴力解法如下,时间复杂度O(n2):
private int maxStart; private int maxLen; public String longestPalindrome(String s) { if (s.length() <= 1) { return s; } char[] arr = s.toCharArray(); for (int i = 0, len = arr.length - 1; i < len; i++) { findLen(i, i + 1, arr); findLen(i - 1, i + 1, arr); } if (maxLen > 0) { return s.substring(maxStart, (maxStart + maxLen)); } else { return s.substring(0, 1); } } private void findLen(int start, int end, char[] arr) { while (start >= 0 && end < arr.length && arr[start] == arr[end]) { start--; end++; } int currentLen = end - start - 1; if (currentLen > maxLen) { maxLen = currentLen; maxStart = start + 1; } }
无需预插入的Manacher‘s Algorithm改进版,时间复杂度O(n)
public String longestPalindrome(String s) { if (s.length() <= 1) { return s; } char[] arr = s.toCharArray(); int targetId = 0; int targetLen = 0; int maxRight = 0; int id = 0; int[] pLens = new int[arr.length * 2]; for (int i = 0, len = 2 * arr.length; i < len; i++) { int index = i / 2; boolean real = i % 2 == 0; pLens[i] = maxRight > index ? Math.min(pLens[2 * id - i], maxRight * 2 - i) : 1; int left; if (real) { left = index - pLens[i]; } else { left = index - pLens[i] + 1; } int right = index + pLens[i]; while (left >= 0 && right < arr.length && arr[left] == arr[right]) { pLens[i] = pLens[i] + 1; left--; right++; } int newRight = index + pLens[i] - 1; if (newRight > maxRight) { maxRight = newRight; id = i; } if (pLens[i] > targetLen || (real && pLens[i] == targetLen)) { targetId = i; targetLen = pLens[i]; } } targetLen--; int mid = targetId / 2; int start, end; if (targetId % 2 == 0) { start = mid - targetLen; end = start + targetLen * 2 + 1; } else { start = mid - targetLen + 1; end = start + targetLen * 2; } return s.substring(start, end); }
跑分
欢迎关注微信公众号:乒乓狂魔

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
并发编程专题六-线程池的使用与分析
五一要结束了,是时候开始新的一波学习了~ 一、什么是线程池?为什么要用线程池? 线程池(thread pool):一种线程使用模式。线程过多会带来调度开销,进而影响缓存局部性和整体性能。而线程池维护着多个线程,等待着监督管理者分配可并发执行的任务。这避免了在处理短时间任务时创建与销毁线程的代价。线程池不仅能够保证内核的充分利用,还能防止过分调度。 优势: 降低资源的消耗。降低线程创建和销毁的资源消耗; 提高响应速度。例如:线程的创建时间为T1,执行时间T2,销毁时间T3,免去T1和T3的时间 提高线程的可管理性。 二、如何实现一个线程池 根据线程池的概念,如果要自己创建线程池,应该满足一下条件。 保存线程的容器。因为线程必须在池子已经创建好了,并且可以保持住,因此,需要一个容器去保存我们的线程。 可以接受外部任务。线程还要能够接受外部的任务,冰并运行这个任务。 保存任务的容器,有些任务可能来不及执行,因此需要将来不及执行的任务通过容器保存起来。 根据以上的条件以及之前我们学的并发编程知识,我们先手动自己尝试写一个线程池 Code: import java.util.Linked...
- 下一篇
结构型模式:外观模式
文章首发: 结构型模式:外观模式 七大结构型模式之五:外观模式。 简介 姓名 :外观模式 英文名 :Facade Pattern 价值观 :统一口径、一致对外 个人介绍 : Provide a unified interface to a set of interfaces in a subsystem. Facade defines a higher-level interface that makes the subsystem easier to use. 要求一个子系统的外部与其内部的通信必须通过一个统一的对象进行。门面模式提供一个高层次的接口,使得子系统更易于使用。 (来自《设计模式之禅》) 你要的故事 作为开发同学,我们平时打交道最多的就是需求同学和测试同学,公司小的时候,什么事情都全靠吼,工作也直接一对一,一个需求下来,需求同学先跟开发同学一起跟进这个需求,需求开发完成了,需求同学和测试同学沟通了需求的测试要点,测试同学就开测。这个过程中需求一直跟到上线。我们用代码来描述这个过程。 开发同学,负责开发需求。 /** * 开发同学 */ class Developer { ...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7安装Docker,走上虚拟化容器引擎之路
- SpringBoot2全家桶,快速入门学习开发网站教程
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- MySQL8.0.19开启GTID主从同步CentOS8
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题