题解 | #最长回文子串#
最长回文子串
http://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
不是最优解，但是比较好理解。
- 截取两头相等的字符串，进行回文子串判断 （例：abccba）
- 将字串分为左右两部分（ abccba >>> abc : cba ）
- 将后半段进行翻转，与前半段相等即为回文串（cba翻转为abc，与前半段相等）
注意：
- 长度为偶数：可以直接对半分；（abba >>> ab : ba）
- 长度为奇数：不对正中间的字符做判断，以中间字符为基准分为两部分（abuba >>> ab : ba）
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()){
String s = in.nextLine();
int max = 0; // 最长回文子串的长度
for(int i=0;i<s.length();i++){
for(int j=s.length();j>i;j--){ // 从两头开始匹配
if(s.charAt(i) == s.charAt(j-1)){ // 两头的字符相等，即开始判断是否为回文串
String str = s.substring(i,j); // 截取待判断的子串str，将str分为两段，相等即为回文子串
int n = str.length();
String s1 = str.substring(0,n/2); // 前半段
StringBuffer s2; // 后半段，需要分为奇数长度和偶数长度
if(str.length()%2 == 0){ // 偶数长度：直接截取剩下的后半部分
s2 = new StringBuffer(str.substring(n/2));
}else{ // 奇数长度：不判断中间字符，越过中间字符截取剩下的后半部分
s2 = new StringBuffer(str.substring(n/2+1));
}
String t = String.valueOf(s2.reverse()); // 翻转后半段的字符串
if(t.equals(s1)){ // 翻转后的字符串与前半段相等即为回文串
max = n>max ? n:max; // 取长度的最大值
}
}
}
}
System.out.println(max);
}
}
} 
美团公司氛围 1829人发布
