Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
Code
public String longestPalindrome(String s) {
/**
* p[i][j]存储是否为回文串
*/
boolean p[][] = new boolean[s.length()][s.length()];
if(s.equals("")||s.length()==1){
return s;
}
int i;
int j;
for (i=0;i<s.length();i++){
for (j=0;j<s.length();j++){
if(i>=j){//当一个字符的时候为回文串
p[i][j] = true;
}
else{
p[i][j] = false;
}
}
}
int k; //回文串的长度
int maxLen=1;
int m=0;//最长回文串的左下标
int n=0;//右下标
for(k=1;k<s.length();k++){
for (i=0;i+k<s.length();i++){
j=i+k;
if(s.charAt(i)==s.charAt(j)){
p[i][j]=p[i+1][j-1];
if(p[i][j]){
maxLen = k+1;
m=i;
n=j;
}
}
else{
p[i][j]=false;
}
}
}
return s.substring(m,n+1);
}