- 最长回文子串
题目说明
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
- 示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
- 示例 2：
输入: "cbbd"
输出: "bb"
public String longestPalindrome(String s) {
if(s==null||s.length()==1){
return s;
}
int start = 0; int end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s,i,i);
int len2 = expandAroundCenter(s,i,i+1);
int len = Math.max(len1,len2);
if(len>(end-start)){
end = i+len/2;
start = i-(len-1)/2;
}
}
return s.substring(start,end+1); // end+1，如果s的长度为0会越界
}
/**
* 从left何right向两边寻找回文串
* @param s
* @param left
* @param right
* @return
*/
public int expandAroundCenter(String s, int left, int right){
while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
left--;
right++;
}
return right-left-1;
}
复杂度分析
时间复杂度：O(n^2)
)，由于围绕中心来扩展回文会耗去 O(n) 的时间，所以总的复杂度为 O(n^2)。空间复杂度：O(1)
