//大晚上闲的无聊,我就帮忙看了一下,全当复习下数据结构
//首先,这个算法找最长回文字串使用的是穷举所有的中心点来找出长度最大的字符串
//而构成回文无非就两种形式,奇数字符串和偶数字符串
//我就在里面给你做注释了,解释下这个方法的意思
public String longestPalindrome(String s) {
int start = 0, end = 0;
//先解释下循环的意思,每个点都要是尝试一次,就是回文的中心点啦
for (int i = 0; i < s.length(); i++) {
//长度为奇数的回文字符串的中心,最开始是 i=0,即长度是1,肯定是中心点
//举个例子:奇数回文121 中心点可以是1.也可以是2,此时回文长度就是3了
int len1 = expandAroundCenter(s, i, i);//这个方法的作用就是返回回文字符串的长度
//长度为偶数时的回文字符串的中心,和奇数理解一样的,比如说22就是回文,长度为2
int len2 = expandAroundCenter(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 expandAroundCenter(String s, int left, int right) {
int L = left, R = right; //其实这里的left,right就是中心点的坐标嘛,坐标可以是一个,也可以是两个
//循环来得到从中心点开始的最长子回文
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
//这个就是长度嘛,什么,你问为什么减一,好吧,我告诉你
//最后一次循环是长度是多加了2,这个知道吧L--,R++
//实际上公式应该是这样 R -L -2+1; //+1你应该知道吧 123的长度为3-1+1 ==!
return R - L - 1;
} |
天盟APP下载
