leetcode地址：5.最长回文子串
解答参考：动态规划、中心扩散、Manacher算法
问题描述
给字符串s，找出s中最长的回文子串。 例如，给出字符串s='babad '，找出最长的回文子串是' bab '
算法思路
本问题可以采用暴力破解法、中心扩散法、Manacher算法三种方法，本文对暴力破解法进行说明。
暴力法夹在双重指针的两侧，验证是否是回文的子串。 除了列举字符串的左右边界以外，容易想到的是，列举可能出现的回文子串的“中心位置”，从“中心位置”开始尽量扩散，试图得到回文串。 因此，中心扩散法的想法是扫描一个个索引，以这个索引为中心，利用“回文串”的中心对称特征，向两侧扩散，看最多能扩散多少。 列举“中心位置”的时间复杂度为o(n )，从“中心位置”扩散得到“回文子串”的时间复杂度为o(n )，因此时间复杂度可以降低到o ) n^2。 请注意这里的细节。 回文列长度为奇数和偶数时，“回文中心”的形状不同。
奇数回文串的“中心”是具体字符，例如，回文串' aba '的中心是字符' b '； 偶数回文串的“中心”是中间两个字的“间隙”。 例如，回文串' abba '的中心是两个' b '中间的“间隙”。 字符串可能的回文子串的中心在哪里？ 我们可以设计应对这两种情况的方法。
在传递一致的索引码并进行中心扩展的情况下，传递此时得到的回文部分列的长度为奇数的相邻的索引码，如果进行中心扩展，则此时得到的回文部分列的长度为偶数。 以下代码的注释中详细介绍了具体的编码。
公共类解决方案{ publicstringlongestpalindrome (strings ) { int len=s.length )； if(len2) { return s； (} int maxLen=1； string RES=s.substring (0，1 )； //中心位置如果列举到len - 2，则为for(intI=0； i len - 1； I ) stringoddstr=centerspread(s，I，I )； stringevenstr=centerspread(s，I，i 1)； stringmaxlenstr=odds tr.length (evenstr.length )？ oddStr : evenStr； if(Maxlenstr.Length(Maxlen ) { maxLen=maxLenStr.length )； res=maxLenStr； } }返回RES； } privatestringcenterspread (strings，int left，int right )/left=right时，回文中心为1个字符，回文串的长度为奇数//right=left 1时int j=right； while(I=0jlen ) if ) s.charat )==s.charat(j ) ) I----； j； } else { break； (//这里要小心，跳出while循环的时候正好满足s.charat(I )！=s.charat(j )，所以不能取I，不能取jreturns.substring ) I1，j )。 }