//原题来自LeetCode
给定一个字符串，返回其中最长的回文子字符串
这道题目前目前受限于能力，暂时只能通过最暴力的解法来求得其解，即遍历子字符串，找出满足条件的解。下面是未曾优化过的代码，超出了时间限制的，囧（96 / 103 个通过测试用例）
import java.util.ArrayList; import java.util.List; public class solution { public String longestPalindrome(String s) { String result = null; if(isPalindrome(s)) { return s; } List<String> res = new ArrayList<String>();//直接用一个list容器，把所有满足条件的结果通通扔进去 int index = s.length(); int length = 0; for(int i = 0;i <= index; i++) { for(int j = index; j >= i; j--) { String temp = s.substring(i, j); if(isPalindrome(temp)) { res.add(temp); } } } for(String str : res) { if(str.length() >= length) { length = str.length(); result = str; } } return result; } public boolean isPalindrome(String s) { int len = s.length(); for(int i = 0; i < len / 2; i++) { if(s.charAt(i) != s.charAt(len-1-i)) { return false; } } return true; } }
这个思路很直接，不过就是要经过几次遍历，耗时太久，只能在此基础上进行优化：
import java.util.ArrayList; import java.util.List; public class solution { public String longestPalindrome(String s) { String result = ""; if(isPalindrome(s)) { return s; } int index = s.length(); int length = 0; for(int i = 0;i <= index; i++) { for(int j = index; j >= i; j--) { String temp = s.substring(i, j); if(isPalindrome(temp)&& temp.length() > length) { length = temp.length(); result = temp; break; //在此跳出循环的原因是我从字符串的最末端开始遍历，遇到的第一个满足条件的，长度肯定是最长的 }
//在剩余的字符串的长度比目前的result要短时也不用比较了，即使有回文串，长度也不会比当前的result要长 if(j - i >= length) { break; } } } return result; } public boolean isPalindrome(String s) { int len = s.length(); for(int i = 0; i < len / 2; i++) { if(s.charAt(i) != s.charAt(len-1-i)) { return false; } } return true; } }
这个目前还真的没有想到其他巧妙的解法，只能日后求助大神再作优化。
原文：https://www.cnblogs.com/WakingShaw/p/11306095.html