Skip to main content

5 Longest Palindromic Substring

LeetCode

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"


从最长的回文开始尝试,成功就返回。时间复杂度 o(n2)。不知道还有没有更好的方法。

class Solution {
public String longestPalindrome(String s) {
int len = s.length();
for(int i=len-1;i>=0;--i){
for(int begin=0; begin+i<len;++begin){
String ret = isPalindrome(s,begin, begin+i);
if(ret!=null) return ret;
}
}
return null;
}

private String isPalindrome(String s, int i, int j){
int left=i, right=j;
while(left<right){
if(s.charAt(left) == s.charAt(right)){
left++;
right--;
} else {
return null;
}
}
return s.substring(i,j+1);
}

}