1、前言
这题目的思路就是双指针从某一个点，向两边扩展，还需要考虑奇偶情况。
题目描述
2、思路
采用中心向两边扩展的方法。答题模版如下：
for 0 <= i < len(s):
找到以 s[i] 为中心的回文串
找到以 s[i] 和 s[i+1] 为中心的回文串
更新答案
此题还可以使用动态规划的方法来做，定义 dp[j][i] 为 j 到 i 是否是回文串，如果 s[j] == s[i] 时，dp[j + 1][i - 1] 也是回文串，那么字符串从 j 到 i 是回文串，即 dp[j][i] = true。
3、代码
public class LongestPalindrome {
/**
* 中心向两边扩展
* @param s
* @return
*/
public String longestPalindrome(String s) {
String res = "";
for(int i = 0; i < s.length(); i++){
String s1 = palindRom(s, i, i);
String s2 = palindRom(s, i, i + 1);
String str = s1.length() > s2.length() ? s1 : s2;
res = res.length() > str.length() ? res : str;
}
return res;
}
private String palindRom(String s, int l, int r) {
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
return s.substring(l + 1, r);
}
/**
* 动态规划
* @param s
* @return
*/
public String longestPalindrome2(String s) {
int m = s.length();
boolean[][] dp = new boolean[m][m];
String res = "";
for(int i = 0; i < m; i++){
for(int j = 0; j <= i; j++){
if(s.charAt(j) == s.charAt(i) && (i - j < 2 || dp[j + 1][i - 1])){
dp[j][i] = true;
if(dp[j][i] && i - j + 1 > res.length()){
res = s.substring(j, i + 1);
}
}
}
}
return res;
}
public static void main(String[] args) {
String s = "babad";
System.out.println(new LongestPalindrome().longestPalindrome2(s));
}
}
