首页 > 代码库 > 【LeetCode】Longest Palindromic Substring 解题报告
【LeetCode】Longest Palindromic Substring 解题报告
DP、KMP什么的都太高大上了,自己想了个朴素的遍历方法。
【题目】
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
【思路】(应该算是O(n)吧)
从中间向两端搜索,分别找到以每个字母为中心的最长回文子串,如果两边剩余的元素已经比当前最长回文子串的一半还短时,停止遍历。
大家别看代码长,是为了便于理解的。
【Java代码】
public class Solution { public String longestPalindrome(String s) { int len = s.length(); if (s == null || len == 1){ return s; } String ret = ""; int mid = len / 2; int i = 0; while (true) { //遍历到s两端时,如果以mid+i或mid-i为中心的最长回文都不比当前最优解长,遍历结束 if (2*(len-(mid+i)) < ret.length() && 2*(mid-i+1) < ret.length()) { break; } String str1 = palindrome1(s, mid+i); String str2 = palindrome2(s, mid+i); String str3 = palindrome1(s, mid-i); String str4 = palindrome2(s, mid-i); if (str1.length() > ret.length()) { ret = str1; } if (str2.length() > ret.length()) { ret = str2; } if (str3.length() > ret.length()) { ret = str3; } if (str4.length() > ret.length()) { ret = str4; } i++; } return ret; } //找出s中以index为中心的aba型的回文子串 public String palindrome1(String s, int index) { String ret = ""; int i = index, j = index; while (i>=0 && j<s.length()) { if (s.charAt(i) != s.charAt(j)) { break; } ret = s.substring(i, j+1); i--; j++; } return ret; } //找出s中以index和index+1为中心的abba型回文子串 public String palindrome2(String s, int index) { String ret = ""; int i = index, j = index+1; while (i>=0 && j<s.length()) { if (s.charAt(i) != s.charAt(j)) { break; } ret = s.substring(i, j+1); i--; j++; } return ret; } }
【分析】
后来在网上找了类似的解法。如 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html ,为了不用区分aba型和abba型的回文子串,构造了一个新的字符串 t ,在两端和每两个字母之间插入一个特殊字符 ‘#’ ,这样当以‘#’为中心的回文子串就是我的代码中abba型子串。
我的代码与之相比还使用了一个小trick,即从中间向两端遍历,这样如果中间已经有比较长的回文子串了,那么两端比较偏的回文子序列就可省去判断。
一遍就AC了,后来比较了网上的解法,不禁为自己有点小激动呢~。
分析可能有误,也许只是自我感觉良好,欢迎大家指正!
【LeetCode】Longest Palindromic Substring 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。