求最长回文字串
声明
方法均是学习参考leetcode的算法，自己学习，都是自己做下总结，并保存记录。因为很多算法没给代码参考，所以我自己实现的代码在这保存一下。有什么不对的地方，各位大佬轻点喷。。。
下面是leetcode的链接：
leetcode（中文版）链接：最长回文子串
题目描述
leeticode 的描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
方法1：利用最长公共子串
下面是leetcode原话
算法
有些人会忍不住提出一个快速的解决方案，不幸的是，这个解决方案有缺陷(但是可以很容易地纠正)：
反转 SS，使之变成 S’S‘ 。找到 SS 和 S’S’ 之间最长的公共子串。然后判断他们的索引是否相同。
如果相同，那么我们尝试更新目前为止找到的最长回文子串；如果不是，我们就跳过这个候选项并继续寻找下一个候选。
这给我们提供了一个复杂度为 O(n的平方) O(n 的平方）动态规划解法，它将占用 O(n^2)O(n 的平方 ) 的空间（可以改进为使用 O(n)O(n) 的空间）。
最长公共字串可以参考这篇文章：最长公共子串
因为这个算法Leetcode没给参考代码，
下面是我实现的代码：有什么错误的地方，各位大佬轻点喷
import java.util.HashMap;
import java.util.Map;
public class leetcode1 {
//主函数
public static void main(String[] args) {
String aabb="abac";
System.out.println(longestPalindrome(aabb));
}
//实现方法
public static String longestPalindrome(String s) {
char[] ss=s.toCharArray();
String zchw="";
String sf="";
//得到s反
for(int i=s.length()-1;i>=0;i--){
sf+=ss[i];
}
//求s与s反的最长公共字串，并判断索引
int[][] aa = new int[s.length()][s.length()];
/*构造字符矩阵如：
* a b a c
* c 1
* a 1
* b 2
* a 1 3
* 斜线最长的为最长字串 aba
* **/
int max=-1,zzb=0;//记录最大值和所在行纵坐标
int sfysy=0;//用来计算字符串反的原y轴索引。s.chat(j)是原字符串y轴索引
for(int i=0;i<s.length();i++) {
for(int j=0;j<s.length();j++) {
if(sf.charAt(i)!=s.charAt(j)) aa[i][j]=0;//判断索引是否相同。
else {
if(i==0||j==0) aa[i][j]=1;
else aa[i][j]=aa[i-1][j-1]+1;
sfysy=s.length()-1-(i-aa[i][j]+1);
if(sfysy==j) {
if(aa[i][j]>=max) {
max=aa[i][j];
zzb=i;
}
}
}
}
}
for(int i=zzb,j=0;j<max;i--,j++) {
zchw+=sf.charAt(i);
}
return zchw;
}
}
算法2暴力法
额。。。。这个我就不写了。要看的自己去看。。。
算法3动态规划
这个方法是改进暴力法。
下面是代码：
class Solution {
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
String answer="";
int max=1;//记录最长回文的字符数，因为空的判断完了，至少是1
int hwt=0;//记录最长回文字符的开始索引
//按照leetcode算法理解所有的1字母就是从索引从第一个开始了。。第0个左边没有了不用看
//同理不用运行到最右边的一个
for(int i=1;i<s.length()-1;i++) {
for(int j=1;;j++) {
if((i-j)<0||(i+j)>=s.length()) break;//达到边界直接跳出这个循环
//如果左右相同记录一下继续判断下一个，否则跳出
if(judgepij(s,i-j,i+j)) {
if((1+j*2)>=max) {
max=1+j*2;
hwt=i-j;
}
}
else break;
}
}
//接下来是有两个一样字母的如:aa,bb这种的,为了防止直接有aab这种，所以老老实实从第0个开始。。。。
//但是出现abb就不用慌，本来就向后比了一个
for(int i=0;i<s.length()-1;i++) {
//首先找连续的一样的,找到了再开始循环如果之前max小于2，这里要跟新一***意这个细节
if(s.charAt(i)==s.charAt(i+1)) {
if(max<2) {
max=2;
hwt=i;
}
for(int j=1;;j++) {
if((i-j)<0||(i+1+j)>=s.length()) break;//达到边界直接跳出这个循环
if(judgepij(s,i-j,i+1+j)) {
if((2+j*2)>=max) {
max=2+j*2;
hwt=i-j;
}
}
else break;
}
}
}
//已经找到了max和hwt，下面获得这个数组就行了
for(int i=hwt,j=0;j<max;i++,j++) {
answer+=s.charAt(i);
}
return answer;
}
public static boolean judgepij(String s,int i,int j) {
if(s.charAt(i)==s.charAt(j)) return true;
else return false;
}
}
这个感觉还能优化，希望大佬能提提意见，我只是把leetcode里面算法实现一下。。要喷的大佬轻点。。
算法4中心扩展算法
官方源码：
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);//我们不难发现这个方法是查找1字母回文的长度
int len2 = expandAroundCenter(s, i, i + 1);//这个是查找2字母回文的长度
int len = Math.max(len1, len2);//选这两个里面最大的
//end-start就是当前回文长度，如果len大于当前就进行刷新
if (len > end - start) {
start = i - (len - 1) / 2;//刷新回文头索引，至于为什么是i-(len-1)/2,因为如果len是偶数如abba
//从bb往两边找，i的值是1
//start = i - len/ 2+1=1-4/2+1=0;把这个换成start = i - （len-1）/ 2=1-3/2=0也对，就是把那个1再len里面减了
//如果是奇数如aba，此时i=1， start = i - (len - 1) / 2=1-2/2=0;
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;//得到长度
}
官方代码很短，这个和上面的动态规划其实思想差不多的，就是从中心开始，初始化是1的就以单字母往两边找，二字母回文就直接从这两个字母往两边找。如abba,这里2字母回文从bb往两边开始查找。
区别就是他一次遍历直接把一字母的和二字母的找完了
并且代码简短了许多，减少了空间浪费。将空间复杂度o(n的平方)减少到了o(1)。
各位大佬有比官方更优解吗，希望分享一下。