例题:
分析:
先给出以下字符串,找出最长的回文子串
由题可知,最长的回文子串为 bcbabcb , 长度为7。
我们可以利用 中心开发思想 寻找最长回文子串,简单说就是以一个字符为中心点,由中心点向两边扩散,如果两边的字符相等,则继续扩散,直至两端的字符不相等,此时就找到了最长回文子串的左右边界(left,right)。
根据数组的遍历顺序,一开始以字符b为中心点,并记录此时回文子串的长度,如果后续找到了更长的回文子串,则替换之前的长度。如下图所示:
遍历数组一个一个往后找中心字符。
在这里发现字符b两端的字符相等,扩大范围。此时回文长度更新为3。依次类推....
但是在这里我们还遗漏了一种情况,我们只考虑了中心字符为奇数的情况, 中心字符为偶数 的情况未必比 中心字符为奇数 的长度短。
比如一开始以字符b和c作为中心点,向两边扩散。但这样显然不行,因为b、c不一样,必须找到两个一样的字符作为中心点。如下图:
注意:以两个字符作为中心点的时候,i不要遍历到数组末尾元素,否则会索引越界。
代码实现:
public class LongestPalindromeLeetcode5 { public static void main(String[] args) { System.out.println(longestPalindrome("babad")); // bab System.out.println(longestPalindrome("cbbd")); // bb System.out.println(longestPalindrome("a")); // a } static int left; static int right; public static String longestPalindrome(String s) { left = 0; right = 0; char[] chars = s.toCharArray(); for (int i = 0; i < chars.length - 1; i++) { extend(chars, i, i); //一个字符作为中心点 extend(chars, i, i + 1); //两个字符作为中心点 } return new String(chars, left, right - left + 1); } /** * 中心开发方法 * @param chars 要遍历的字符数组 * @param i 中心点索引 * @param j 中心点索引 */ public static void extend(char[] chars, int i, int j){ //遇到相同字符则向左右两边扩散 while(i >= 0 && j < chars.length && chars[i] == chars[j]){ i--; j++; } //已经不是回文了,需要把i和j拉回边界 i++; j--; if(j - i > right - left){ left = i; right = j; } } }
猜你喜欢
- 14天前(2020海丝之路文化博览会)2023海丝之路文化和旅游博览会开幕
- 14天前(fender japan hybrid)Fender东京旗舰店盛大开幕在即,开售商品和店内服务提前揭晓
- 14天前(万达酒店及度假村连续五年荣获“中国饭店集团60强”)万达酒店及度假村连续五年荣获“中国饭店集团60强”
- 14天前(夏日旅行海报)夏日旅行|精简行囊 向快乐进发
- 14天前(罗马尼亚的匈牙利族自治)江苏赴匈牙利、罗马尼亚开展文旅交流推广活动
- 14天前(云南滇陇工程咨询有限公司)陇滇携手谋发展 文旅合作谱新篇
- 14天前(新西兰“空降”上海:新西兰旅游局邀请你来“玩真的”!)新西兰“空降”上海:新西兰旅游局邀请你来“玩真的”!
- 14天前(札幌小樽市)2024年暑期飞往北海道避暑吧!札幌小樽city walk路线推荐
- 14天前(马尔代夫华尔道夫酒店多少钱)Chef Zhao就任马尔代夫伊挞富士岛华尔道夫酒店Li Long中餐厅新主厨
- 14天前(锦州新增两家国家aaa级旅游景区有哪些)锦州新增两家国家AAA级旅游景区
网友评论
- 搜索
- 最新文章
- (2020广州车展哈弗)你的猛龙 独一无二 哈弗猛龙广州车展闪耀登场
- (哈弗新能源suv2019款)智能科技颠覆出行体验 哈弗重塑新能源越野SUV价值认知
- (2021款全新哈弗h5自动四驱报价)新哈弗H5再赴保障之旅,无惧冰雪护航哈弗全民电四驱挑战赛
- (海南航空现况怎样)用一场直播找到市场扩张新渠道,海南航空做对了什么?
- (visa jcb 日本)优惠面面俱到 JCB信用卡邀您畅玩日本冰雪季
- (第三届“堡里有年味·回村过大年”民俗花灯会活动)第三届“堡里有年味·回村过大年”民俗花灯会活动
- (展示非遗魅力 长安启源助力铜梁龙舞出征)展示非遗魅力 长安启源助力铜梁龙舞出征
- (阿斯塔纳航空公司)阿斯塔纳航空机队飞机数量增至50架
- (北京香港航班动态查询)香港快运航空北京大兴新航线今日首航
- (我在港航“呵护”飞机 每一次安全着陆就是最好的荣誉)我在港航“呵护”飞机 每一次安全着陆就是最好的荣誉
- 热门文章