給你一個字符串 s怔球，找到 s 中最長的回文子串塔猾。
示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案环础。
示例 2：
輸入：s = "cbbd"
輸出："bb"
示例 3：
輸入：s = "a"
輸出："a"
示例 4：
輸入：s = "ac"
輸出："a"
提示：
1 <= s.length <= 1000
s 僅由數(shù)字和英文字母（大寫和/或小寫）組成
1荸百、暴力解法
遍歷所有的子串闻伶，并判斷每一個子串是否為回文串，最后即可得到最長的回文子串够话。
class Solution {
public String longestPalindrome(String s) {
int length = s.length();
int maxLength = 0;
String res = "";
for(int subLength = 1; subLength <= length; subLength++){
for(int index = 0; index + subLength <= length; index++){
String subStr = s.substring(index, index + subLength);
if(isPalindrome(subStr)){
if(subStr.length() > maxLength){
maxLength = subStr.length();
res = "" + subStr;
}
}
}
}
return res;
}
public boolean isPalindrome(String s){
int length = s.length();
int left = 0;
int right = length - 1;
while(left <= right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
兩層for循環(huán)進行兩次遍歷蓝翰，判斷回文串也要進行一次遍歷光绕，則時間復雜度達到了O(n3)，直接提交會超時畜份。但是參考官方題解诞帐，暴力解法也是能通過的。在以上解法中每判斷一次回文子串都需要截取一次字符串爆雹，會有額外的性能消耗停蕉，則不再截取字符串，只記錄最長回文子串的起始位置和長度钙态，最后返回的時候再截取子串慧起。當字符串長度為1時不需要判斷直接返回即可。進行剪枝操作后可勉強通過册倒。
//執(zhí)行用時：2850 ms
class Solution {
public String longestPalindrome(String s) {
int length = s.length();
if(length < 2){
return s;
}
int maxLength = 1;
int resLeft = 0;
for(int subLength = 2; subLength <= length; subLength++){
for(int index = 0; index < length - subLength + 1; index++){
if(isPalindrome(s, index, index + subLength - 1)){
if(subLength > maxLength){
maxLength = subLength;
resLeft = index;
}
}
}
}
return s.substring(resLeft, resLeft + maxLength);
}
public boolean isPalindrome(String s, int left, int right){
int indexL = left;
int indexR = right;
while(indexL <= indexR){
if(s.charAt(indexL) != s.charAt(indexR)){
return false;
}
indexL++;
indexR--;
}
return true;
}
}
時間復雜度：O(n3)
空間復雜度：O(1)蚓挤，僅消耗常數(shù)空間
