大家好，又见面了，我是你们的朋友全栈君。
中心扩展法
主要思路是每次选一个中点，然后向两边扩展，找出以该中点对应的最长的回文串的长度，然后维护一个全局的最长回文串长度变量。
对于奇偶数长度的不同处理方式：
expandAroundCenter方法中如果传入同一个点的索引，则表示以该点为中心，对应着探索字符串长度为奇数的情况- 如果传入两个点的索引，则表示以这两个点之间为中心，对应着探索字符串长度为偶数的情况
/** * @Classname Solution5 * @Description TODO * @Date 2019/12/9 9:45 * @Created by Cheng */
public class Solution5 {
/** * 中心扩展法 * @param s * @return */
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
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);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
// 注意此时L和R都已经在有效范围外，所以长度是R-L-1
return R - L - 1;
}
}
马拉车
具体思路有必要单独写一篇
/** * @Classname Solution5 * @Description TODO * @Date 2019/12/9 9:45 * @Created by Cheng */
public class Solution5 {
/** * 马拉车 * @param s * @return */
public static String longestPalindrome2(String s) {
//处理字符串
List<Character> list = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
list.add('#');
list.add(s.charAt(i));
}
list.add('#');
int[] dp = new int[list.size()];
int resLen = 0;
int resCenter = 0;
int maxR = 0;
int maxM = 0;
for (int i = 1; i <list.size() ; i++) {
dp[i] = maxR>i?Math.min(dp[maxM*2-i],maxR-i):1;
while((i-dp[i])>=0 && (i+dp[i])<list.size() && list.get(i+dp[i]) == list.get(i-dp[i]))
dp[i]++;
if (i + dp[i] > maxR) {
maxR = i+dp[i];
maxM = i;
}
if (resLen < dp[i]) {
resLen = dp[i];
resCenter = i;
}
}
StringBuilder ret = new StringBuilder();
for (int i = resCenter-resLen+1; i <=resCenter+resLen-1 ; i++) {
if(list.get(i)!='#')
ret.append(list.get(i));
}
return ret.toString();
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/164003.html原文链接：https://javaforall.net
