这是一道LeetCode上的题目，题目原题如下：
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input:"babad"
Output:"bab"
Note:"aba" is also a valid answer.
Example:
Input:"cbbd"
Output:"bb"
简单理解一下题目就是给定一个字符串，求解其中最长的回文字符子串。什么是回文字符串呢？简单的说就是字符串从左到右读和从右到左读一样。
解法一
看到这个题目，首先想到的是可以利用堆栈的方法，将字符串一个字符一个字符的入栈，然后下一个字符和栈顶的字符进行比较，如果一样，将字符出栈到一个临时字符串中，用于比较。实现代码如下：
import java.util.ArrayList;
class Solution {
public String longestPalindrome(String s) {
String result = "";
ArrayList charList = new ArrayList();
byte[] bytes = s.getBytes();
String temp = "";
boolean isAddChar = false;
for (int i = 0; i < bytes.length; i++){
byte topChar1 = 0;
byte topChar2 = 0;
if (charList.size() > 0){
topChar1 = charList.get(0);
}
if (charList.size() > 1){
topChar2 = charList.get(1);
}
if (topChar1 == bytes[i]){
temp = String.format("%c%s%c", topChar1, temp, bytes[i]);
charList.remove(0);
isAddChar = true;
}else if (topChar2 == bytes[i]){
temp = String.format("%c%c%s%c", topChar2, topChar1, temp, bytes[i]);
charList.remove(0);
charList.remove(0);
isAddChar = true;
}else{
if (i > 1 && bytes[i] == bytes[i-1]){
temp = String.format("%s%c", temp, bytes[i]);
isAddChar = true;
}else {
if (isAddChar) {
if (result.length() < temp.length()) {
result = temp; temp = "";
}
}
charList.add(0, bytes[i]);
}
}
}
if (result.length() < temp.length()) {
result = temp;
}
if (result.isEmpty()){
return String.format("%c", bytes[0]);
}
return result;
}
}
然而得到的结果并非最长字符串，而是最短的字符串。
解法二
解法一不通过，于是换了一个思路来解决问题。解决思路是遍历字符串，发现两个字符或者三个字符能够构成回文字符串的时候，迅速作前后字符的搜索，扩大该回文字符串的长度，最后记录最长的回文字符串，得到结果。
代码如下：
import java.util.ArrayList;
class Solution {
public String longestPalindrome(String s) {
int len = 1;
int start = 0;
int lenTemp = 0;
byte[] bytes = s.getBytes();
for (int i = 1; i < bytes.length; i++){
if (i < bytes.length - 1 && bytes[i-1] == bytes[i+1]){
int j = 1;
lenTemp = 1;
while(bytes[i-j] == bytes[i+j]){
lenTemp +=2;
if (i-j == 0 || i+j == bytes.length-1){
break;
}else{
j++;
}
}
if (lenTemp > len){
len = lenTemp;
start = i - lenTemp/2;
}
}
if(bytes[i-1] == bytes[i]){
int j = 1;
lenTemp = 0;
while(bytes[i-j] == bytes[i+j-1]){
lenTemp += 2;
if (i-j == 0 || i+j-1 == bytes.length-1){
break;
}else{
j++;
}
}
if (lenTemp > len){
len = lenTemp;
start = i - lenTemp/2;
}
}
}
return s.substring(start, len + start);
}
}
