【力扣】5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//暴力破解
        //时间复杂度 O(n^3)
        //空间复杂度 O(1)
    //那就找到所有的子串，挨个遍历，直到找到最长的子串
    public String longestPalindrome(String s) {

        //若是长度，不足，则返回原字符串
        if(s.length() <= 1){
            return s;
        }

        int start = 0,maxLen = 1;

        char[] charArray = s.toCharArray();

        int length = s.length();

        for(int i = 0; i < length -1 ; i++){

            for( int j = i+1; j< length ;j++){
                if(j - i + 1 > maxLen && isPalindrome(charArray,i,j)){
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substring(start,start + maxLen);
        
    }



    /**
    * 判断是否为回文子串
    **/
    public boolean isPalindrome(char[] charArray , int start, int end){
        while(start < end){
            if(charArray[start] != charArray[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

//动态规划
    //时间复杂度O(n^2)
    //空间复杂度O(n^2)
    public String longestPalindrome(String s) {
        //若是长度，不足，则返回原字符串
        if(s.length() <= 1){
            return s;
        }


        //动态规划最重要的就是找到公式
            //

        int start = 0, maxLen = 1; //定义最大长度，以及当前最大长度的初始位置

        char[] charArray = s.toCharArray();

        int length = s.length();

        // dp[i][j] 表示 s[i, j] 是否是回文串
        boolean[][] dp = new boolean[length][length];

        //初始化开始值，这个二维数组的斜线为true
        for(int i = 0; i < length ; i++){
            dp[i][i] = true;
        }

        //你可能回疑问，为什么要这么循环
            //例子：
                //假如我们要求值：F(1,4) 的是否为回文串，而且 arr[1] = arr[4] ，那么我们应该想要知道 F(2,3)是不是回文串，那么就要在f(1,4)之前求出来f(2,3)的值。
        for(int j = 1; j < length ; j++){
            for( int i = j-1; i>=0 ;i--){
                //假设当前字符串的left ！= right
                if(charArray[i] != charArray[j]){
                    dp[i][j] = false;
                } else {
                    //若是当前字符串的left == right
                    if(j - i < 3){
                        //当前字符串长度为3个，直接设置为true
                        dp[i][j] = true;
                    } else {
                        //需要看下里面的子串是否为回文串
                        dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j] && j - i + 1 > maxLen){
                        start = i;
                        maxLen = j-i+1;
                    }
                }
            }
        }
        return s.substring(start,start + maxLen);
    }

中心扩散：

public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0, 1);
        // 中心位置枚举到 len - 2 即可
        for (int i = 0; i < len - 1; i++) {
            String oddStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    private String centerSpread(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0 && j < len) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
        return s.substring(i + 1, j);
    }

在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。

引用：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/