对 hard 类型的题，表示目前实在是 hold 不住，暂时先不刷啊。等我刷完 easy 和 medium 回头再战！ 2016/10/10
编程语言是 Java，代码托管在我的 GitHub 上，包括测试用例。欢迎各种批评指正！
<br />
题目 —— Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 10000, and there exists one unique longest palindromic substring.
<br >
解答
题目大意
给出一个字符串 S，找出 S 的最长回文子串，也就是最长的对称子串。可以假设 S 最长为 1000，且只存在一个最长子串。-
解题思路
- 首先考虑既然是对称子串的话，长度值可能有两种：奇数和偶数，我们利用这两种方式来扩展子串。
- 设置两个全局变量，一个保存子串的最低位置，一个保存子串长度，用来返回我们需要的子串。
代码实现
public class Solution {
private int maxLen;
private int low;
public String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
}
for (int i = 0; i < s.length()-1; i++) {
extendPalindrome(s, i, i);
extendPalindrome(s, i, i+1);
}
return s.substring(low, low + maxLen);
}
public void extendPalindrome(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
if (maxLen < j - i - 1) {
maxLen = j - i - 1;
low = i + 1;
}
}
}
-
小结
思路不是很难，但求解该题需要注意细节和边界条件。第一个，是对方法中 i 和 j 值的限定。i 如果取 i > 0 的话，那么对于 "bb" 这种字符串就会求解错误。第二个，是 maxLen 比较的对象，是 j - i - 1，在 i 和 j 的值变了以后，是不满足循环条件的，所以我们要取上一次改变的值。
