Longest Palindromic Substring
给一个字符串, 返回其中最长的回文子字符串. 这个题非常经典, 做法是写一个辅助方法, 可以从字符串中某一个位置向外找到最长的回文 (利用回文的性质), 然而我们不知道回文是奇数位还是偶数位, 所以我们找的时候, 需要同时考虑.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class Solution { public String longestPalindrome(String s) { int start = 0; int end = 0; for(int i = 0 ; i < s.length(); i++){ int len1 = expand(s,i,i); int len2 = expand(s,i,i+1); int len = Math.max(len1,len2); if(len > end - start) { start = i - (len-1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } public int expand (String s, int l, int r) { while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){ l--; r++; } return r - l - 1; } } |