## leetcode——Longest Palindromic Substring

2018年04月12日 ⁄ 综合 ⁄ 共 1158字 ⁄ 字号 评论关闭

Given a string S,
find the longest palindromic substring in
S.
You may assume that the maximum length of
S is
1000, and there exists one unique longest palindromic substring.

1000之内暴力可以解决。关键就是，如何考虑aa的情况。aba这种情况，挨个字母探索就行。问题就是偶数对称的情况。

AC代码：

```public class Longest_Palindromic_Substring {
private int maxLen = -1;
private int start = -1;
private int end = -1;

private int findLongest(char[] ss, int idx){
int i=1;
for(;idx+i<ss.length && idx-i>=0 && ss[idx+i]==ss[idx-i];i++);
return i-1;
}
public String longestPalindrome(String s) {
char[] ss = s.toCharArray();
StringBuffer sb = new StringBuffer("");
for(char c:ss){
sb.append(' ');
sb.append(c);
}
sb.append(' ');

char[] bb = sb.toString().toCharArray();

for(int i=1;i<bb.length-1;i++){
int tmp = findLongest(bb,i);
if(maxLen<tmp){
maxLen=tmp;
start = i-maxLen;
end = i+maxLen;
}
}
if(start==-1){
start = 0;
end = 0;
}
String sbb = sb.toString().substring(start,end+1);
return sbb.replaceAll(" ","");
}

public static void main(String[] args){
Longest_Palindromic_Substring longest_palindromic_substring = new Longest_Palindromic_Substring();
System.out.println(longest_palindromic_substring.longestPalindrome("a"));
}
}```