题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
例子
示例 1：输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。
示例 2：输入：s = "cbbd"输出："bb"
示例 3：输入：s = "a"输出："a"
示例 4：输入：s = "ac"输出："a"
复制代码
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/longest-palindromic-substring，著作权归领扣网络所有。
思路以及解答
暴力破解
暴力破解，即是针对里面每一个子串，都去判断是否为回文串。
判断每一个字符是不是回文串，比如用 cbac 判断，左右两个指针，对称判断，相等则往中间移动，继续判断，不相等则直接返回 false 。
public static String longestPalindrome(String s) { if (s == null || s.length() == 0) { return s; } String result = s.substring(0, 1); for (int i=0; i < s.length() - 1; i++) { for (int j = i + 1; j < s.length(); j++) { if (judge(s, i, j) && j - i + 1 > result.length()) { result = s.substring(i, j+1); } } } return result; } // 判断每个子串是不是回文 public static boolean judge(String source, int start, int end) { // 对称轴对比 while (start <= end) { if (source.charAt(start) != source.charAt(end)) { return false; } start++; end--; } return true; }
复制代码
暴力破解复杂度过高，会超时，不推荐使用。
中心拓展法
回文串总是中心对称的，前面使用暴力法的时候，都是截取出子串之后再判断，只有判断到全部对称，才能证明回文，这样其实走了很多弯路，只要最后一个不对称，前功尽弃。
反过来想，我们不如在每一个点，都尝试往两边拓展，这样只要不匹配，就可以及时止顺。
值得注意的是，中心拓展法的中心怎么找？3 个字符有多少个中心呢？
一共有五个中心，有些中心可能是两个字符的间隙，有些中心可能是字符。那么设计的时候，我们用 left 和 right 表示两个指针：
具体实现如下：
class Solution { // 开始下标 public static int start = -1; // 最大长度 public static int maxLen= 0; public String longestPalindrome(String s) { start = -1; maxLen = 0; if(s==null||s.length()==0){ return ""; } for(int i=0;i<s.length();i++){ // 以当前字符为对称轴 judge(s,i,i); // 以当前字符和下一个字符的间隙为对称轴 judge(s,i,i+1); } if(start == -1){ return ""; } return s.substring(start,start+maxLen); }
public void judge(String s,int left,int right){ while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){ left--; right++; } int size = right-left-1; if(size > maxLen){ maxLen = size; start = left+1; } }}
复制代码
动态规划
其实，一个字符串是回文串的话，那么它倒过来读也是一样的，也就是说，它与它反转后的字符串，其实是完全匹配的，那么要是我们用一个字符串和它反转字符串一一统计匹配，是不是就可以得到结果呢？
答案是肯定的！假设原字符串为 s1，反转后的字符串为 s2，字符串长度为 n，我们用数组 nums[n][n] 来记录匹配的数量，nums[i][j]表示以 s1[i] 结尾的字符子串，和以 s2[j]结尾的字符子串，两者的匹配字符的最大数值。
当 s1[i] == s2[j]:
如果 i == 0 或者 j == 0: nums[i][j] = 1
否则 nums[i][j] = nums[i - 1][j - 1] + 1;
如果 s1[i] ！= s2[j]，则 nums[i][j]=0
前面说的其实就是状态转移表达式，也就是 nums[i][j] 是怎么求解的？nums[i][j] 是依赖于 nums[i - 1][j - 1] 和 当前字符是否匹配，如果当前字符不匹配，直接赋值为 0，只有在当前字符匹配的情况下，才会需要看前面一位的匹配数值 nums[i - 1][j - 1]。
假设以 babad 为例子：
最后两行的计算：
实现的代码如下：
class Solution { public static String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } if (s.length() == 1) { return s; } int len = s.length(); String s1 = new StringBuffer(s).reverse().toString(); int[][] nums = new int[len][len]; int end = 0, max = 0; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { if (s1.charAt(i) == s.charAt(j)) { if (i == 0 || j == 0) { nums[i][j] = 1; } else { nums[i][j] = nums[i - 1][j - 1] + 1; } } if (nums[i][j] > max) { if (len - i - 1 + nums[i][j] - 1 == j) { end = j; max = nums[i][j]; } } } } return s.substring(end - max+1, end+1); }}
复制代码
作者简介
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
剑指Offer全部题解PDF
2020年我写了什么？
开源编程笔记
评论