5. 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

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

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力法

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;}
}

中心扩散法

参考文献

点击跳转

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