当前位置 博文首页 > 一条IT:【leetcode刷题】20.最长回文子串——Java版
?欢迎订阅《leetcode》专栏,每日一题,每天进步?
回文的意思是正着念和倒着念一样,如:上海自来水来自海上
——leetcode此题热评
在对联中就有回文的手法,“上海自来水来自海上”,大家有下联了吗
哈喽,大家好,我是一条。
糊涂算法,难得糊涂
今天来一道中等题,看看自己功力几何?
难度:中等
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
示例 3:
输入:s = "a" 输出:"a"
示例 4:
输入:s = "ac" 输出:"a"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成Solution
之前我们做过一道题是:最长不重复子串。当时使用的是
滑动窗口法
。这道题增加了回文的约束,那么该怎么处理回文,可以在纸上写一个回文串观察一下,有什么特点呢?
从中心点向两端发散
对吧,所以我们要滑动这个中心点,并对每一个中心点,进行左右扩展,判断左右字符是否相等即可。
- 把
null
和空字符串的特殊情况处理掉- 有一个可滑动且大小可变的窗口,窗口左端(start)不动,右端(end)向后移动
- 由于字符串长度有奇数和偶数两种,所以我们需要同时计算从一个字符开始扩展和从两个字符之间开始扩展
- 找出两种扩展中相对长的作为当前最大值
- 新的
start
要从何处开始,如何扩展字符串只需要考虑的问题还有一种马拉车算法更加快速,但有一定难度,面试一般不会出现,感兴趣的同学可以看一下
Code
所有
leetcode
代码已同步至github欢迎
star
/** * @author yitiaoIT */ class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1; }
Result
复杂度分析
- 时间复杂度:O(N)
🌈寻宝
?今天是坚持刷题更文的第20/100天
?各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
?更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝,礼尚往来,给大家准备了一条多年积累下来的优质资源,包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找,寻宝游戏现在开始。
找不到可以评论留言,一条就会注意到你。
如果还不行,请私信我。
cs下一篇:没有了
最新 更多<<
一条IT:【leetcode刷题】20.最长回文子串——Java版 一条IT:【python实战】不玩微博,一封邮件就能知道实时热榜,天 数据库天地:[MSSQL]SQL简繁转换函数 weixin_33736048的博客:笨兔兔的故事(中) 沉默王二:教妹学Java(二十四):一文了解 Java 中的方法 AS_TianKong的专栏:【分享】下辈子我还做一个快乐的程序员 我一定要成为测试开发!:今天开始学java(十四):抽象类、接口 刘桂林:掌握RxJava的葵花宝典 爱.NET:《当程序员的那些狗日日子》三 chenchw的博客:学习linux chenchw的博客:编程建议(看视频总结) chenchw的博客:2021-06-28-用户管理 chenchw的博客:chmod的数字表示法介绍 chenchw的博客:chmod的演练- -R递归修改目录权限和相关复习 chenchw的博客:Java基础1 chenchw的博客:2021-06-28-Java小基础 chenchw的博客:系统信息相关命令/磁盘空间查看情况 chenchw的博客:ps top kill 进程信息 chenchw的博客:2021-06-29 chenchw的博客:JDK JRE chenchw的博客:安装JDK /环境变量 chenchw的博客:详细注释Hello,World程序 chenchw的博客:2021-06-30tips chenchw的博客:在java中什么是编译,什么是运行 chenchw的博客:JAVA开发注意事项和细节说明(重点中的重点) lzh_2_4的博客:各种笔记 RtxTitanV的博客:Java并发总结之线程池 God_Y:编程面试题整理 晴天的专栏:怎样规划你毕业以后的人生 流年的博客:C++语言篇 字符串及字符数组练习