題目描述
給定一個字符串派继，求字符串的最長回文子串
解法
- 中心擴(kuò)散法
- 動態(tài)規(guī)劃法
中心擴(kuò)散法
從一個點(diǎn)出發(fā)哼审，比較周圍的字符能否加入到回文串中，如果可以听怕，更新回文串長度
public static String reseveString(String str){
int start = 0;//最長回文串開始的標(biāo)志
int maxLen = 0;//最長回文串的長度
//考慮aba的部分
for(int i = 1; i < str.length()-1;i++){
int left = i-1;
int right = i+1;
while(left >= 0 && right <str.length()&&str.charAt(left)==str.charAt(right)){
if(maxLen < right - left + 1){
start = left;
maxLen = right - left + 1;
}
left--;
right++;
}
}
// 考慮abba情況
for(int i = 0; i < str.length()-1;i++){
int left = i;
int right = i + 1;
while(left >= 0 && right < str.length()&& str.charAt(left)==str.charAt(right)){
if(maxLen < right - left + 1){
start = left;
maxLen = right - left + 1;
}
left--;
right++;
}
}
return str.substring(start,start+maxLen);
}
動態(tài)規(guī)劃
dp[i][j] = dp[i-1][j+1]+2
當(dāng)前回文串基于子串
public static String reserveDp(String str){
int start = 0;
int end = 0;
int maxLen = 0;
boolean dp[][] = new boolean[str.length()][str.length()];
for(int j = 0; j < str.length();j++){
for(int i = 0; i < j;i++){
if(str.charAt(i)==str.charAt(j)&&(j-i<=2||dp[i+1][j-1])){
dp[i][j] = true;
if(maxLen < j - i + 1){
maxLen = j - i + 1;
start = i;
end = j;
}
}
}
}
if(start == end){
return Character.toString(str.charAt(0));
}
return str.substring(start,start+maxLen);
}
