题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

题解

方法一：暴力法

思路

遍历所有子字符串，判断是否为回文字符串。

算法

public String longestPalindrome(String s) { if(s == null || s.length() < 1) { return ""; } int start = 0; int end = 0; int len = 0; for(int i=0;i<s.length();i++) { for(int j=i;j<s.length();j++) { if(isPalindrome(s, i, j)) { if(j-i+1 > len) { len = j-i+1; start = i; end = j; } } } } return s.substring(start, end+1); } private boolean isPalindrome(String s, int left, int right) { while(left < right) { if(s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; }

复杂度分析

时间复杂度：O(n^3)？ 。

空间复杂度：常数？。

方法二：中心扩展法

思路

回文字符串具有左右两端相互对称的特点。如果回文字符串的长度为奇数，则对称中心为中间的一个字符；如果回文字符串的长度为偶数，则对称中心为中间的两个字符。两种情况分别如下图所示：

为了求一个字符串S的最长回文子字符串，可以依次以字符串S中的每个字符为回文子串的中间字符向两边扩散得到回文子串，并同时考虑回文子串长度为奇数和偶数的情况，求出该回文子串的长度并更新最大回文子串长度。

算法

方法expand以字符串s中的left、right位置的字符向两边扩散，得到以left和right为中心的回文子串的最大长度。当left=right时，表示回文子串的长度为奇数，当left=right-1时，表示回文子串的长度为偶数。

public String longestPalindrome(String s) { if(s == null || s.length() < 1) { return ""; } int start = 0; int end = 0; int max = 0; for(int i=0;i<s.length();i++) { int len1 = expand(s, i, i); int len2 = expand(s, i, i+1); int len = Math.max(len1, len2); if(len > max) { max = len; start = i - (len-1)/2; end = i + len/2; } } return s.substring(start, end + 1); } private int expand(String s, int left, int right) { while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }

复杂度分析

时间复杂度：O(n^2)？ 。

空间复杂度：常数？。