LeetCode:最长回文子串
一、题目还原
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
二、解题思路
1）Solution1 暴力解法
① 双层循环，逐一比对是否为回文子串。记录最长子串
2）Solution2 中心扩散法
① EdgeCase:判空返回""，只有一个字符返回该字符
② 以任意一点 j 为回文子串的中心点向两边扩散,向左left --，向右right ++
③ 根据奇偶判定，如果是奇数，left = j - 1; right = j + 1，偶数则left = j , right = j + 1
④ 根据是否越界，以及left和right所对应的值是否相等条件返回左右下标，截取子串
⑤ 如果遍历到最后发现得不到超过一个字符的回文子串，则返回第一个字符
三、代码展示
① main函数
public static void main(String[] args) {
String s = "cyyoacmjwjubfkzrrbvquqkwhsxvmytmjvbborrtoiyotobzjmohpadfrvmxuagbdczsjuekjrmcwyaovpiogspbslcppxojgbfxhtsxmecgqjfuvahzpgprscjwwutwoiksegfreortttdotgxbfkisyakejihfjnrdngkwjxeituomuhmeiesctywhryqtjimwjadhhymydlsmcpycfdzrjhstxddvoqprrjufvihjcsoseltpyuaywgiocfodtylluuikkqkbrdxgjhrqiselmwnpdzdmpsvbfimnoulayqgdiavdgeiilayrafxlgxxtoqskmtixhbyjikfmsmxwribfzeffccczwdwukubopsoxliagenzwkbiveiajfirzvngverrbcwqmryvckvhpiioccmaqoxgmbwenyeyhzhliusupmrgmrcvwmdnniipvztmtklihobbekkgeopgwipihadswbqhzyxqsdgekazdtnamwzbitwfwezhhqznipalmomanbyezapgpxtjhudlcsfqondoiojkqadacnhcgwkhaxmttfebqelkjfigglxjfqegxpcawhpihrxydprdgavxjygfhgpcylpvsfcizkfbqzdnmxdgsjcekvrhesykldgptbeasktkasyuevtxrcrxmiylrlclocldmiwhuizhuaiophykxskufgjbmcmzpogpmyerzovzhqusxzrjcwgsdpcienkizutedcwrmowwolekockvyukyvmeidhjvbkoortjbemevrsquwnjoaikhbkycvvcscyamffbjyvkqkyeavtlkxyrrnsmqohyyqxzgtjdavgwpsgpjhqzttukynonbnnkuqfxgaatpilrrxhcqhfyyextrvqzktcrtrsbimuokxqtsbfkrgoiznhiysfhzspkpvrhtewthpbafmzgchqpgfsuiddjkhnwchpleibavgmuivfiorpteflholmnxdwewj";
//String s = "ac";
System.out.println("longestPalindrome最长回子串 === "+longestPalindrome(s));
System.out.println("longestPalindrome2最长回子串 === "+longestPalindrome2(s));
}
② longestPalindrome方法函数
//暴力法，超时！
public static String longestPalindrome(String s) {
String maxStr = "";
int maxLength = 0;
if(null != s && !"".equals(s)){
for(int i = 0; i<=s.length() ; i++){
for(int j = i; j <= s.length() ; j++){
String s1 = s.substring(i,j);
if(s1.contentEquals(new StringBuffer(s1).reverse())){
if(maxLength < s1.length()){
maxLength = s1.length();
maxStr = s1;
}
}
}
}
}
return maxStr;
}
控制台输出：
longestPalindrome最长回子串 === xrcrx
Process finished with exit code 0
虽然该方法得到结果正确，但是在提交后直接超出了时间限制
③ longestPalindrome2和expand方法函数
//中心扩散法
public static String longestPalindrome2(String s) {
//判空
if(null == s || s.isEmpty()){
return "";
}
//只有一个数字的时候
if(s.length() == 1){
return s;
}
int maxLength = 0;
String maxStr = "";
String[] arr = s.split("");
int j = 0;
while(j<arr.length){
//奇数情况
int a[] = expand(arr,j-1,j+1);
//偶数情况
int b[] = expand(arr,j,j+1);
if(a[1] - a[0] > b[1] - b[0] && a[1] - a[0] > maxLength){
maxLength = a[1] - a[0];
maxStr = s.substring(a[0],a[1]+1);
}else if(b[1] - b [0] > maxLength){
maxLength = b[1] - b[0];
maxStr = s.substring(b[0],b[1]+1);
}
j++;
}
//不是回文字符，返回第一个字符
if(maxLength == 0){
maxStr = arr[0];
}
return maxStr;
}
//向两边扩展判断是否为回文字符，返回数字a[0]为左下标，a[1]为右下标
public static int[] expand(String[] arr, int left, int right){
int a[] ={0,0};
if(left < 0){
a[0] = 0;
a[1] = 0;
return a;
}else if(right >= arr.length){
a[0] = arr.length - 1;
a[1] = arr.length - 1;
return a;
}
while(left > -1 && right < arr.length && arr[left].equals(arr[right])){
left -- ;
right ++;
}
a[0] = left+1;
a[1] = right-1;
return a;
}
控制台输出：
longestPalindrome2最长回子串 === xrcrx
Process finished with exit code 0
四、自我总结
这是LeecCode题库的第五题，难度为中等，博主今日可栽跟头了，一开始就想用暴力解法两层循环把所有情况都遍历一遍进行比对，这样的做法虽然稳妥，但是在执行效率上非常的低，双层循环中套了一个比较回文数，使用了reverse()方法，相当于三层循环，时间复杂度为O(n3)，第一次提交也就是失败了。
继续之前的优化思路，为了减少循环层数，博主最先想到的是中心扩散法，一个字符串进行遍历，在进行中心扩散，其最坏时间复杂度才为O(n2)，相比暴力解法优化了许多，但是未考虑“”、单字符以及没有超过单字符的回文子串这些EdgeCase，在提交n次失败后才顺利提交成功，但从提交的成绩来看还是有待提升的，看到评论区大神大多说用动态规划的思路，博主后期也会研究研究，继续提升自我！
- 博主最近也将刷题的代码上传到github中，欢迎各位大佬们指点一二
Github仓库地址：https://github.com/w735937076/LeetCode
上一篇： leetcode最长回文子串
下一篇： 数组总结