本文共 2150 字，大约阅读时间需要 7 分钟。
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"Output: "bab"Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"Output: "bb"
思路一：求每一个子串，但是要知道一个技巧就是如何截取从最大串到最小串的判断。时间复杂度是O(N^3)
class Solution { public String longestPalindrome(String s) { //O(N^3)的时间复杂度 if(s.length() <= 1) return s; for(int i = s.length(); i >= 0; i--) { for(int j = 0; j <= s.length() - i; j++) { //关键在于这个截取的子串，由长到短，这个是最关键的 String subStr = s.substring(j, i+j);//从外向内收缩的子串,截取的子串越来越短 int count = 0; for(int k = 0; k < subStr.length()/2; k++) { if(subStr.charAt(k) == subStr.charAt(subStr.length() - k -1))//判断是不是回文 count++; } if(count == subStr.length() / 2)//第一次出现的回文就是最长的 return subStr; } } return ""; } } 思路二：马拉车算法，时间复杂度为O(N),具体算法过程看
马拉车的算法核心就是以当前节点为中心点，求当前这个点的最大回文串。而关键的步骤就是如何加快这个扩散。 马拉车算法分为两大部分： 1、当前节点i在右边界mx外，直接暴力扩散 2、当前节点i在右边界内： （1）i的对称点i在最大左右边界L内，则i的回文串长度为i的回文串长度 （2）i的对称点i在最大左右边界L外，则i的回文串长度为到R的距离。 （3）i的对称点i在最大左右边界L上，则i的回文串要计算R之后的那部分是否是回文串class Solution { public String longestPalindrome(String s) { //马拉车算法O(N)的时间复杂度 if(s.length()==0) return ""; StringBuilder t = new StringBuilder("$#"); for(int i = 0; i < s.length(); i++) { t.append(s.charAt(i)); t.append('#'); } t.append('@'); int[] p = new int[t.length()]; int mx = 0; int id = 0; int resLen = 0; int resCenter = 0; for(int i = 1; i < t.length()-1; ++i) { //关键算法步骤，mx > i表示当前点在右边界内还是外？如果是外，则重新开始扩散也就是等于1， //当在右边界里面的时候，则判断对称点i*半径有没有超过左边界，判断两者拿个比较短，就是哪个。 //p[2 * id - i]表示没有超过的长度，mx-i表示超出的时候的长度 p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1; //如果对称点的长度比当前的还长,后面的是否匹配要自己去算 while (((i - p[i])>=0) && ((i + p[i]) 转载地址：http://nxrai.baihongyu.com/