題目描述

給你一個字符串 s，找到 s 中最長的回文子串。

如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。

示例 1：

輸入：s = “babad”
輸出：“bab”
解釋：“aba” 同樣是符合題意的答案。
示例 2：

輸入：s = “cbbd”
輸出：“bb”

提示：

1 <= s.length <= 1000
s 僅由數(shù)字和英文字母組成

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/longest-palindromic-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

暴力法

class Solution {public String longestPalindrome(String s) {int len=s.length();if (len<2){return s;}int maxLen=1;int begin=0;char[] charArray=s.toCharArray();for (int i=0;i<len-1;i++){for(int j=i+1;j<len;j++){if(j-i+1>maxLen&&validPalindrome(charArray,i,j)){maxLen=j-i+1;begin=i;}}}return s.substring(begin,begin+maxLen);}private static boolean validPalindrome(char[] charArray, int left, int right) {while (left<right){if (charArray[left]!=charArray[right]){return false;}left++;right--;}return true;}
}

中心擴散法

參考文獻

點擊跳轉(zhuǎn)

https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/