题目描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
输入: "cbbd"
输出: "bb"
解题思路
- 遍历字符串,以每个字符为中心展开,向左右两侧寻找回文串。再以两个字符之间为中心展开,向左右两侧寻找回文串。
代码
public String longestPalindrome(String s) {
if (s == null || s.length() <= 0) {
return null;
}
int start = 0;
int end = 0;
int maxLength = 0;
for (int i = 0; i < s.length(); i++) {
int length1 = expandCenter(s, i, i);
int length2 = expandCenter(s, i, i + 1);
if (maxLength < Math.max(length1, length1)) {
maxLength = Math.max(length1, length1);
start = i - (maxLength - 1) / 2;
end = i + maxLength / 2;
}
}
return s.substring(start, end + 1);
}
private int expandCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
网友评论