给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
思路
我们用一个 boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[l][r]=true，我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符，是不是减少了很多重复计算。
```java
public static String longestPalindrome2(String s) {
int len = s.length();
if(len <= 1) return s;
//字符串为空或者长度等于1，直接返回
boolean[][] dp = new boolean[len][len];
//记录每一个子串的状态，dp[i][j]=true表明，以i为起点，j为终点的子串是回文
int max = 0;
//最大回文长度
String ret = s.substring(0, 1);
//存放回文，初始化为s的第一个字符，假如该字符串没有回文，那就直接返回字符串的第一个字符
for(int r = 1; r < len; r++){
for(int l = 0; l < r; l++){
//这两个循环很关键，
if(s.charAt(r) == s.charAt(l) && (r - l <= 2 || dp[l+1][r-1])){
dp[l][r] = true;
if(max < r - l + 1) {
max = r - l + 1;
//max值更新
ret = new String(s.substring(l, r + 1));
//存放新的回文
}
}
}
}
return ret;
}
## 1 判断一个字符串是否是回文串（左右对称）
单个数字默认为是
public class isPlalindrome {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入字符串：");
String str = sc.nextLine();
System.out.println(isPlalindrome(str));
}
public static boolean isPlalindrome(String str) {
//将字符串转化为字符数组
char[] array=str.toCharArray();
int left=0,right=array.length-1;//记录数组的开始位置和结束位置
while(left<right)//开始位置小于结束位置时，进行判断 两位置处于对称位置上
{
if(array[left++]!=array[right--])//如果两位值的字符不相同 则不对称
return false;//返回false
}
//所有位除奇数位时的中间位均对应 返回true
return true;
}
}
## 2 暴力法
public class Violent {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入字符串：");
String str = sc.nextLine();
String output = longestPlalindrome(str);
System.out.println(output);
}
/**************************
* 求解字符串的最长回文串----暴力法 O(n^3)
* 通过两层循环找出字符串的所有子串 对每一个子串进行判断
* 将是回文串的子串储存 当有新的回文串时，比较记录中的回文串和当前回文串的长度
* 用较长的串替换当前串 如果两串长度相同，保留旧的
* PS：如果想保存所有的回文串 可以修改记录回文串的结构为String数组（链表、hash表都可以）
* @param str 要求解的字符串
* @return 返回字符串中的最长回文串
*/
public static String longestPlalindrome(String original)
{
//非空判断
if((original==null)||original.length()==0)
{
return null;
}
//将字符串转换为字符数组
char[] oriArray=original.toCharArray();
int first=0;
int end=0;//当前字符串中回文串的始末位置 包含末位置
for(int i=0;i<oriArray.length-1;i++)//两次循环 查找字符串的所有子串
{
for(int j=i;j<oriArray.length;j++)
{
//判断子串是否为回文串
int left=i,right=j;//记录左侧右侧的位置
while(left<right)//左侧下标小于右侧下标时 比较未完成
{
if(oriArray[left]!=oriArray[right])
break;//如果出现对称位置不相等元素 则不是回文串跳出循环
//判断下一对称位置
left++;
right--;
}
if(left>=right)//是否比较完成 是字符串是否为回文串的判断条件
{
if(j-i>end-first)//查找到回文串 且长度大于当前存储的回文串长度
{
//替换当前回文串
first=i;
end=j;
}
}
}
}
//查找结束 将数组转化为字符串返回
return String.valueOf(oriArray, first, end+1);
}
}
## 3 动态规划
为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显， “ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。
动态规划
动态规划一般用于（1）求最大最小值（2）求可行不可行（3）求方案总数。如果题目是求所有可行的方案，则肯定是不能用DP来做的。
思考动态规划的第一点----最优子结构：
思考动态规划的第二点----子问题重叠：
思考动态规划的第三点----边界：
思考动态规划的第四点----子问题独立：
思考动态规划的第五点----做备忘录：
思考动态规划的第六点----时间分析：
动态规划不是算法，它是一种方法，它是在一件事情发生的过程中寻找最优值的方法，因此，我们需要对这件事情所发生的过程进行考虑。而通常我们从过程的最后一步开始考虑，而不是先考虑过程的开始。
小技巧
解题思路
动态规划的话需要二维数组，一维肯定是不够的， 因为最终返回的是字符串。肯定要知道起始的串和结束的串，然后
dp[i][j]字符串从i到j是否为回文串，如果是当前的长度是j-i+1
dp方程 s[i]==s[j] dp[i][j] = dp[i+1][j-1]
解析1
public static String longestPalindrome2(String s) {
int len = s.length();
if(len <= 1) return s;
//字符串为空或者长度等于1，直接返回
boolean[][] dp = new boolean[len][len];
//记录每一个子串的状态，dp[i][j]=true表明，以i为起点，j为终点的子串是回文
int max = 0;
//最大回文长度
String ret = s.substring(0, 1);
//存放回文，初始化为s的第一个字符，假如该字符串没有回文，那就直接返回字符串的第一个字符
for(int r = 1; r < len; r++){
for(int l = 0; l < r; l++){
//这两个循环很关键，
if(s.charAt(r) == s.charAt(l) && (r - l <= 2 || dp[l+1][r-1])){
dp[l][r] = true;
if(max < r - l + 1) {
max = r - l + 1;
//max值更新
ret = new String(s.substring(l, r + 1));
//存放新的回文
}
}
}
}
return ret;
}
## 4 中心扩展算法
事实上，只需使用恒定的空间，我们就可以在 O(n^2)的时间内解决这个问题。我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 12n−1 个这样的中心。
你可能会问，为什么会是 2n - 12n−1 个，而不是 nn 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 \textrm{“abba”}“abba” 的中心在两个 \textrm{‘b’}‘b’ 之间）。
评论1
终于看懂了这个中心扩展算法是什么意思了。 先来解释一下为什么中心是2n-1而不是n 比如有字符串abcba，这时回文子串是abcda，中心是c；又有字符串adccda，这时回文子串是adccda，中心是cc。 由此可见中心点既有可能是一个字符，也有可能是两个字符，当中心为一个字符的时候有n个中心，当中心为两个字符的时候有n-1个中心，所以一共有2n-1个中心。 然后for循环开始从左到右遍历，为什么会有两次expandAroundCenter，一次是i和i本身，一次是i和i+1，这就是上面说到的一个中心与两个中心。 而后会去判断这两种情况下谁的回文子串最长，并标记出这个子串在原字符串中的定位，即start和end。
import java.util.Scanner;
/*
* @Author liuhaidong
* @Description 中心扩展算法
* @Date 10:01 2019/9/16 0016
**/
public class ExpandAroundCenter {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入字符串：");
String str = sc.nextLine();
String output = longestPalindrome(str);
System.out.println(output);
}
/*
* @Author liuhaidong
* @Description 最长回文串
* @Date 9:50 2019/9/16 0016
**/
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1)
{
return "";
}
int start = 0, end = 0;
//子串在原字符串中的定位
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
//判断奇数个 abcba
int len2 = expandAroundCenter(s, i, i + 1);
//判断偶数个 abba
int len = Math.max(len1, len2);
//比较两个谁更长
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
//以上是不懂意思
}
return s.substring(start, end + 1);
}
/*
* @Author liuhaidong
* @Description 中心结点法
* @Date 9:50 2019/9/16 0016
**/
private static int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
}
## 5 Manacher
首先，Manacher算法提供了一种巧妙地办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑，具体做法是，在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现，一般情况下可以用#号。下面举一个例子：
Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度，比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。
京公网安备 11010502036488号