5.最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路：
首先想到暴力匹配，两个循环，搜索出所有长度大于等于2的子串，然后进行回文判断，使用一个最大的长度变量，和起始位置。
class Solution {
//暴力匹配
public String longestPalindrome(String s) {
int n=s.length();
int maxlen=1;
int begin=0;
//这里抖个小机灵，如果使用s.charAt(i),底层函数会每次都要进行边界判断。速度慢
char []chars=s.toCharArray();
if(n<2){
return s;
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(maxlen<j-i+1&&validPalindromic(chars,i,j)){
maxlen=j-i+1;
begin=i;
}
}
}
return s.substring(begin,begin+maxlen);
}
private boolean validPalindromic(char[] chars, int i, int j) {
while(i<j){
if(chars[i]!=chars[j]){
return false;
}
i++;
j--;
}
return true;
}
} 时间复杂度巨高！O(N3)，两层for循环，里面还套着一个回文检测函数。 思路二：
LeeCode刷题日记 文章被收录于专栏
包含解法，高频leecode算法题。
查看7道真题和解析
