给定一个字符串 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
  
 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190916201338279.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTU2MzE2MQ==,size_16,color_FFFFFF,t_70)

       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。