LeetCode/5. 最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

非常经典的题目，这里忽略暴力解法和Manacher算法只记录动态规划和中心扩散法。首先介绍动态规划方法，基于这样的思想，如果一个子串是回文子串，那么该子串掐头去尾后依然是回文字符串，用一个二维数组记录，dp[i][j]表示s[i,j]是否是回文子串

具体代码如下：

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2)
            return s;
        int maxLength = 1;
        int start = 0;

        //可以不初始化对角线的值，因为对角线的值不会被其它位置参考
        boolean[][] dp = new boolean[n][n];
        //列向递增计算，保证前一列最下方的值被先计算出来，保证后一列状态转移方程不会缺失值
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j))
                    dp[i][j] = false;
                else {
                    //边界条件，如果只有两个或者三个字符，其中两边的字符相同，那么这是一个回文子串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}

还有一种中心扩散方法，从某个位置开始，依次向外扩散，求取最长回文子串，这种方法需要考虑当前位置为惠子子串的中心，该中心是奇数位置还是偶数位置，所以需要考虑两种情况，最后返回较长的子串即可

具体代码如下：

class Solution {
    //中心扩散法需要考虑中心位置是奇数还是偶数
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2)
            return s;

        int maxLength = 1;
        int start = 0;

        for (int i = 0; i < n - 1; i++) {
            int oddLength = help(s, i, i);
            int evenLength = help(s, i, i + 1);

            int curMaxLength = Math.max(oddLength, evenLength);
            if (curMaxLength > maxLength) {
                maxLength = curMaxLength;
                //中心为奇或者偶的统一规律
                start = i - (maxLength - 1) / 2;
            }
        }
        return s.substring(start, start + maxLength);
    }

    private int help(String s, int left, int right) {
        int n = s.length();
        int i = left;
        int j = right;

        while (i >= 0 && j < n) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else
                break;
        }
        //结束条件为s.charAt(i) != s.charAt(j)
        //回文串长度为j - i + 1 - 2 = j - i - 1
        return j - i - 1;
    }
}