题解 | #最长对称子字符串#
最长对称子字符串
https://www.nowcoder.com/practice/93f6c5b032bf473696373ab0d834b0fc
刷无重复最长子串时想到了这个问题，而之前做过一次这个题，借鉴别人的代码写出来了，但是理解并不深刻，这次根据做无重复最长子串问题从前往后搜寻不重复子串的思路，遂想到往上面套，暴力破解，虽然笨拙，但是理解起来方便易实现。
大体思路就是从头到尾去搜寻最长的对称子字符串，用一个指针标记当前搜索的位置，也即最左边的字符，然后从最大范围(当前位置到字符串末尾)考虑，这里我之前想通过中间指针来处理两侧移动问题，后面发现存在奇偶长度不好处理，最后想到了做二分查找时用到的处理方式，就是首尾指针向中间靠拢，左指针大于右指针时结束，可以很好解决奇偶情况下中间指针不好处理的问题，代码如下，欢迎交流。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String a = sc.next();
System.out.println(getMaxSubStr(a));
}
}
public static String getMaxSubStr(String s) {
char[] sarr = s.toCharArray();
int i, j, len, bg, ed, maxLen = 0, left = 0, right = 0;
len = sarr.length;
for (i = 0; i < len; i ++) {
for (j = len - i; j > 0; j-- ) {
for (bg = i, ed = i + j - 1; bg <= ed; bg++, ed--) {
if (sarr[bg] != sarr[ed]) {
break;
}
}
if (bg > ed) { //全部对称
if (j > maxLen) {
maxLen = j;
left = i;
right = i + j - 1;
}
break;
}
}
}
return s.substring(left, right + 1);
}
}
投递谷歌等公司10个岗位 >
