中心扩散法 时间复杂度 O(n^2)
从当前字符向左右扩展,逐一判断是否是相等,相等就说明还是回文串,分为两者情况
1.奇数回文串 left = i, right = i
2.偶数回文串 left = i, right = i + 1
优化前代码
class Solution {
public String longestPalindrome(String s) {
char[] sc = s.toCharArray();
int n = sc.length;
int max = 1, ll = 0, rr = 0;
for(int i = 0; i < n; i ++ ) {
int l = i - 1, r = i + 1;
while(0 <= l && r < n && sc[l] == sc[r]) {
l --;
r ++;
}
if(max < r - l - 1) {
max = r - l - 1;
ll = l + 1;
rr = r - 1;
}
l = i;
r = i + 1;
while(0 <= l && r < n && sc[l] == sc[r]) {
l --;
r ++;
}
if(max < r - l - 1) {
max = r - l - 1;
ll = l + 1;
rr = r - 1;
}
}
return s.substring(ll, ll + max);
}
}
优化后的代码 — 可读性优化
奇数时,无所谓,统一都可以
偶数时,是从i - i + 1之间一刀切形成左右相等,i已经占据一个字符串长度了,所以需要减一,从而通过整除让其少减1
start = i - (maxlen - 1) / 2;
end = i + maxlen / 2;
class Solution {
public int expandCenter(String s, int left, int right) {
int L = left, R = right;
while(0 <= L && R < s.length() && s.charAt(L) == s.charAt(R)) {
L --;
R ++;
}
return R - L - 1;
}
public String longestPalindrome(String s) {
int max = 1, start = 0, end = 0;
for(int i = 0; i < s.length(); i ++) {
int one = expandCenter(s, i, i);
int two = expandCenter(s, i, i + 1);
int maxlen = Math.max(one, two);
if(maxlen > end - start + 1) {
start = i - (maxlen - 1) / 2;
end = i + maxlen / 2;
}
}
return s.substring(start, end + 1);
}
}
666