517，最长回文子串的3种解决方式
The real opportunity for success lies within the person and not in the job.
成功的真正机会在于人而非工作。
问题描述
给你一个字符串s，找到s中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
暴力求解
暴力求解是最容易想到的，要截取字符串的所有子串，然后再判断这些子串中哪些是回文的，最后返回回文子串中最长的即可。
这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串的长度，最后再截取。代码如下
1public String longestPalindrome(String s) {
2 if (s.length() < 2)
3 return s;
4 int start = 0;
5 int maxLen = 0;
6 for (int i = 0; i < s.length() - 1; i++) {
7 for (int j = i; j < s.length(); j++) {
8 //截取所有子串，然后在逐个判断是否是回文的
9 if (isPalindrome(s, i, j)) {
10 if (maxLen < j - i + 1) {
11 start = i;
12 maxLen = j - i + 1;
13 }
14 }
15 }
16 }
17 return s.substring(start, start + maxLen);
18}
19
20//判断是否是回文串
21private boolean isPalindrome(String s, int start, int end) {
22 while (start < end) {
23 if (s.charAt(start++) != s.charAt(end--))
24 return false;
25 }
26 return true;
27}
暴力求解毕竟效率很差，上面代码其实还可以优化一下，在截取的时候，如果截取的长度小于等于目前查找到的最长回文子串，我们可以直接跳过，不需要再判断了，因为即使他是回文子串，也不可能是最长的。
1public String longestPalindrome(String s) {
2 if (s.length() < 2)
3 return s;
4 int start = 0;
5 int maxLen = 0;
6 for (int i = 0; i < s.length() - 1; i++) {
7 for (int j = i; j < s.length(); j++) {
8 //截取所有子串，如果截取的子串小于等于之前
9 //遍历过的最大回文串，直接跳过。因为截取
10 //的子串即使是回文串也不可能是最大的，所以
11 //不需要判断
12 if (j - i < maxLen)
13 continue;
14 if (isPalindrome(s, i, j)) {
15 if (maxLen < j - i + 1) {
16 start = i;
17 maxLen = j - i + 1;
18 }
19 }
20 }
21 }
22 return s.substring(start, start + maxLen);
23}
24
25//判断是否是回文串
26private boolean isPalindrome(String s, int start, int end) {
27 while (start < end) {
28 if (s.charAt(start++) != s.charAt(end--))
29 return false;
30 }
31 return true;
32}
中心扩散法
中心扩散法也很好理解，我们遍历字符串的每一个字符，然后以当前字符为中心往两边扩散，查找最长的回文子串，下面随便举个例子，看一下视频演示（如果觉得视频播放过快，可以点击暂停）
视频中我们是以每一个字符为中心，往两边扩散，来求最长的回文子串。但忽略了一个问题，回文串的长度不一定都是奇数，也可能是偶数，比如字符串"abba"，如果使用上面的方式判断肯定是不对的。
我们来思考这样一个问题，如果是单个字符，我们可以认为他是回文子串，如果是多个字符，并且他们都是相同的，那么他们也是回文串。
所以对于上面的问题，我们以当前字符为中心往两边扩散的时候，先要判断和他挨着的有没有相同的字符，如果有，则直接跳过，来看下代码
1String longestPalindrome(String s) {
2 //边界条件判断
3 if (s.length() < 2)
4 return s;
5 //start表示最长回文串开始的位置，
6 //maxLen表示最长回文串的长度
7 int start = 0, maxLen = 0;
8 int length = s.length();
9 for (int i = 0; i < length; ) {
10 //如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
11 // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
12 if (length - i <= maxLen / 2)
13 break;
14 int left = i, right = i;
15 while (right < length - 1 && s.charAt(right + 1) == s.charAt(right))
16 ++right; //过滤掉重复的
17 //下次在判断的时候从重复的下一个字符开始判断
18 i = right + 1;
19 //然后往两边判断，找出回文子串的长度
20 while (right < length - 1 && left > 0 && s.charAt(right + 1) == s.charAt(left - 1)) {
21 ++right;
22 --left;
23 }
24 //保留最长的
25 if (right - left + 1 > maxLen) {
26 start = left;
27 maxLen = right - left + 1;
28 }
29 }
30 //截取回文子串
31 return s.substring(start, start + maxLen);
32}
动态规划
定义二维数组dp[length][length]，如果dp[left][right]为true，则表示字符串从left到right是回文子串，如果dp[left][right]为false，则表示字符串从left到right不是回文子串。
如果dp[left+1][right-1]为true，我们判断s.charAt(left)和s.charAt(right)是否相等，如果相等，那么dp[left][right]肯定也是回文子串，否则dp[left][right]一定不是回文子串。
所以我们可以找出递推公式
1 dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]
有了递推公式，还要确定边界条件：
如果s.charAt(left)！=s.charAt(right)，那么字符串从left到right是不可能构成子串的，直接跳过即可。
如果s.charAt(left)==s.charAt(right)，字符串从left到right能不能构成回文子串还需要进一步判断
如果left==right，也就是说只有一个字符，我们认为他是回文子串。即dp[left][right]=true（left==right）
如果right-left<=2，类似于"aa"，或者"aba"，我们认为他是回文子串。即dp[left][right]=true（right-left<=2）
如果right-left>2，我们只需要判断dp[left+1][right-1]是否是回文子串，才能确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1][right-1]
有了递推公式和边界条件，代码就很容易写了，来看下
1public static String longestPalindrome(String s) {
2 //边界条件判断
3 if (s.length() < 2)
4 return s;
5 //start表示最长回文串开始的位置，
6 //maxLen表示最长回文串的长度
7 int start = 0, maxLen = 1;
8 int length = s.length();
9 boolean[][] dp = new boolean[length][length];
10 for (int right = 1; right < length; right++) {
11 for (int left = 0; left < right; left++) {
12 //如果两种字符不相同，肯定不能构成回文子串
13 if (s.charAt(left) != s.charAt(right))
14 continue;
15
16 //下面是s.charAt(left)和s.charAt(right)两个
17 //字符相同情况下的判断
18 //如果只有一个字符，肯定是回文子串
19 if (right == left) {
20 dp[left][right] = true;
21 } else if (right - left <= 2) {
22 //类似于"aa"和"aba"，也是回文子串
23 dp[left][right] = true;
24 } else {
25 //类似于"a******a"，要判断他是否是回文子串，只需要
26 //判断"******"是否是回文子串即可
27 dp[left][right] = dp[left + 1][right - 1];
28 }
29 //如果字符串从left到right是回文子串，只需要保存最长的即可
30 if (dp[left][right] && right - left + 1 > maxLen) {
31 maxLen = right - left + 1;
32 start = left;
33 }
34 }
35 }
36 //截取最长的回文子串
37 return s.substring(start, start + maxLen);
38}
总结
这题不是很难，上面几种应该都很容易想到。其实还有一种更高效的解决方式就是Manacher算法，很多人习惯把它称为马拉车算法，这种解法比上面几种难度稍微大一些，后续有时间会单独拿出来讲。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有800多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。