leetcode5 -- 最长回文子串

题目描述：

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

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

解决方法：

回文串：正着读和倒着读是一样的

比如：“bab”，倒过来也是“bab”

比如：“shdnndhs”，倒过来也是“shdnndhs”

从另一个方向思考就是，从回文字符串的中间向两侧扩散得到的结果是一样的。

但是这个要分字符串是奇数或者偶数的情况：

1.奇数：比如“cabac”

那么中间的字符是b，向两边扩散分别是“a”，“c”。

2.偶数：比如“bbbb”

那么中间的是“bb”，向两边扩散是“b”。

需要对给定的字符串中的每个字符作考虑，考虑以它为中心能够形成的回文串，长度为奇数或者偶数两种不同的情况要分别判断一下，取长度较长的一种情况。

代码如下：

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}int left = 0, right = 0;int maxLength = 1;int centerIndex = 0;int flag = 1;// 1奇数，2偶数for (int i = 0; i < s.length(); i++) {left = i - 1;right = i + 1;// 奇数情况while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}int len = right - left - 1;if (len > maxLength) {maxLength = len;centerIndex = i;flag = 1;}left = i;right = i + 1;// 偶数情况while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}len = right - left - 1;if (len > maxLength) {maxLength = len;centerIndex = i;flag = 2;}}if (flag == 1) {return s.substring(centerIndex - maxLength / 2, centerIndex + maxLength / 2 + 1);} else if (flag == 2) {return s.substring(centerIndex - maxLength / 2 + 1, centerIndex + maxLength / 2 + 1);} else {return "";}}
}