题目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
代码
int st,end;
@Test
public void test5() {
System.out.println(longestPalindrome2("babad"));
}
public String longestPalindrome2(String s) {
int len = s.length();
if(len < 1) {
return s;
}
char[] chs = s.toCharArray();
for (int i = 0; i < len; i++) {
helper(chs,i,i);
helper(chs,i,i + 1);
}
return s.substring(st,end+1);
}
private void helper(char[] chs,int l,int r) {
while (l >= 0 && r < chs.length && chs[l] == chs[r]) {
--l;
++r;
}
if(end - st < r - l -2) {
st = l + 1;
end = r - 1;
}
}
思路是：中心扩展法
要么是一个数为中心，要么是两个数为中心，然后向两边扩展
