题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例2:
输入: "cbbd"
输出: "bb"
思路
1.可以使用中心扩展法来寻找此题的答案，而一个字符串的中心应该是2n-1个而不是n个，因为两个字母相同的话，该中心在其二者的“夹缝”中。
2.为了分割中心方便，我们可以将每个字母使用特殊符号分割，然后遍历整个字符串，最终寻找到最长子串。
Java代码实现
public static String longestPalindrome(String s) {
String str = "#";
for (int i = 0; i < s.length(); i++) {
str += s.charAt(i)+"#";
}
String longestStr = "";
for (int i = 1; i < str.length(); i++) {
String cur = longestPalindrome(str,i);
if(longestStr.length()<cur.length())
longestStr = cur;
}
return longestStr.replace("#","");
}
private static String longestPalindrome(String s,int index) {
int left = index-1;
int right = index+1;
while(left>=0 && right<s.length()){
if(s.charAt(left) == s.charAt(right)){
left--;
right++;
}else {
break;
}
}
return s.substring(left+1,right);
}
