5. 最长回文子串
问题描述
给你一个字符串 s，找到 s 中最长的回文子串
解题思路
题目的总体思路与昨天求解最长回文子序列的那一题差不多，不过这道题要求返回的是回文子串，所以要找到最长回文子串在s中的起始位置与结束位置。
二维dp数组：dp[i][j]表示s的子串s.substring(i,j+1)是否是回文子串
s.substring(int beginIndex，int endIndex)截取规则：beginIndex =< s的值 < endIndex
image.png
class Solution {
public String longestPalindrome(String s) {
int l = s.length();
if(l < 2){
return s;
}
String res = s.substring(0,1);
boolean[][] dp = new boolean[l][l];
for(int i = l -1; i >=0; i--){
int j = 0;
while(j < i){
//当i>j时，substring(i,j)不存在，所以回文子串不存在
dp[i][j] = false;
j++;
}
//子串中只有一个字符时,一定是回文子串
dp[i][i] = true;
for(j = i + 1; j < l; j++){
if(s.charAt(i) == s.charAt(j)){
if(j-i == 1){
dp[i][j] = true;
}else{
dp[i][j] = dp[i+1][j-1];
}
}else{
dp[i][j] = false;
}
//更新结果子串
if(dp[i][j] && j - i + 1 >= res.length()){
res = s.substring(i,j+1);
}
}
}
return res;
}
}
dp好难，我哭了=.=
唯一的安慰是：每次我熬夜学习的时候，我妹妹都在旁边打游戏陪我。她让我觉得，夜还没有那么深。当然，我不熬夜的时候，她这个点也在打游戏（摊手.jpg）
