题解 | #最长回文子串#

本文仅用于本人学习记录

这篇文章第一次看完全没思路，后来看了题解，哇，除了暴力法外居然还有两种优美的解法——中心扩散法和动态规划法：
动态规划就是dp[left][right]作为状态方程，[left,right]表示是否是回文串。
当right == left时，dp直接true；
当right - left <= 2且[left] == [right]时，dp直接true，这是因为[left,right]只有三位，中间是不用管的，这也算回文串，比如"aba"、"aa"。
当right - left > 2且[left] == [right]时,dp等于dp[left-1][right+1]。
当然一开始就判断[left] == [right]比较好，一开始边缘字符就不相等就不可能是回文串了。
这里要特别注意的是遍历方向，是右指针从1开始遍历到尾，而左指针从0开始遍历到右指针。这样可以保证状态转移的时候前一位是处理过有意义值的。

import java.util.*;

public class Solution {
      public int getLongestPalindrome(String A, int n) {
        // write code here
        boolean[][] dp = new boolean[n][n];
        int maxlen = 1;
        for(int j = 1;j < n;j++){
            for(int i = 0;i < j;i++){
                if(i == j){
                    dp[i][j] = true;
                }
                else if(i + 1 < n && j - 1 >= 0){
                    if(A.charAt(i) == A.charAt(j)){
                        if(j - i <= 2){
                            dp[i][j] = true;
                        }
                        else {
                            dp[i][j] = dp[i+1][j-1];
                        }
                        if(dp[i][j] == true){
                            maxlen = Math.max(maxlen,j-i+1);
                        }
                    }
                }
            }
        }
        return maxlen;
    }
}

我的if-else逻辑可能比较混乱，放个大佬的版本：

    public int getLongestPalindrome(String A, int n) {
        //边界条件判断
        if (n < 2)
            return A.length();
        //start表示最长回文串开始的位置，
        //maxLen表示最长回文串的长度
        int maxLen = 1;
        boolean[][] dp = new boolean[n][n];
        for (int right = 1; right < n; right++) {
            for (int left = 0; left < right; left++) {
                //如果两种字符不相同，肯定不能构成回文子串
                if (A.charAt(left) != A.charAt(right))
                    continue;

                //下面是s.charAt(left)和s.charAt(right)两个
                //字符相同情况下的判断
                //如果只有一个字符，肯定是回文子串
                if (right == left) {
                    dp[left][right] = true;
                } else if (right - left <= 2) {
                    //类似于"aa"和"aba"，也是回文子串
                    dp[left][right] = true;
                } else {
                    //类似于"a******a"，要判断他是否是回文子串，只需要
                    //判断"******"是否是回文子串即可
                    dp[left][right] = dp[left + 1][right - 1];
                }
                //如果字符串从left到right是回文子串，只需要保存最长的即可
                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                }
            }
        }
        //最长的回文子串
        return maxLen;
    }

另外，还有个中心扩散法，就是遍历每个字符，然后以当前字符为中心向左右两边扩散，一旦相同本轮回文串长度就+2，否则结束，然后维护最大值即可。不过当检测到下一个字符跟当前字符相同时要跳过一次，毕竟回文串也可能是偶数。放下大佬的算法：

    public int getLongestPalindrome(String A, int n) {
        //边界条件判断
        if (n < 2)
            return A.length();
        //maxLen表示最长回文串的长度
        int maxLen = 0;
        for (int i = 0; i < n; ) {
            //如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
            // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
            if (n - i <= maxLen / 2)
                break;
            int left = i;
            int right = i;
            while (right < n - 1 && A.charAt(right + 1) == A.charAt(right))
                ++right; //过滤掉重复的

            //下次在判断的时候从重复的下一个字符开始判断
            i = right + 1;
            //然后往两边判断，找出回文子串的长度
            while (right < n - 1 && left > 0 && A.charAt(right + 1) == A.charAt(left - 1)) {
                ++right;
                --left;
            }
            //保留最长的
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
            }
        }
        //截取回文子串
        return maxLen;
    }