题目

Given a string s, return the longest palindromic substring in s.

---

Example1

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example2

Input: s = "cbbd"
Output: "bb"

Example3

Input: s = "a"
Output: "a"

Example4

Input: s = "ac"
Output: "a"

题目大意

就是找出字符串s中最大的回文子串，然后输出。

解题思路

方法一: 暴力匹配

暴力匹配思想很简单，这里不解释太多，很容易通过代码来理解意思。

暴力解法时间复杂度高，但是思路清晰、编写简单。由于编写正确性的可能性很大，可以使用暴力匹配算法检验我们编写的其它算法是否正确。优化的解法在很多时候，是基于“暴力解法”，以空间换时间得到的，因此思考清楚暴力解法，分析其缺点，很多时候能为我们打开思路。

代码

package leetcode;

public class D05_LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();

        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    private boolean validPalindromic(char[] charArray, int left, int right) {
        while(left < right) {
            if(charArray[left] != charArray[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}

复杂度分析

* 时间复杂度：O(N³)这里N是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文，这三种操作都与N相关；
* 空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。

方法二: 动态规划

主要思想是，一个回文，去掉两头以后，剩下的部分依然是回文；
依然从回文串的定义展开讨论：
    · 如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
    · 如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
        a 如果里面的子串是回文，整体就是回文串；
        b 如果里面的子串不是回文串，整体就不是回文串。
即：在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。因此可以把「状态」定义为原字符的一个子串是否为回文子串。

借鉴了LeetCode中大牛的题解。动态规划、中心扩散、Manacher 算法

代码

package leetcode;

public class D05_LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();

        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    private boolean validPalindromic(char[] charArray, int left, int right) {
        while(left < right) {
            if(charArray[left] != charArray[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}

复杂度分析

* 时间复杂度：O(N²)。
* 空间复杂度：O(N²)，二维dp问题，一个状态得用二维有序数对表示，因此空间复杂度是O(N²)。

方法三:中心扩散法

暴力法采用双指针两边夹，验证是否是回文子串。
除了枚举字符串的左右边界以外，比较容易想到的是枚举可能出现的回文子串的”中心位置”，从”中心位置”尝试尽可能扩散出去，得到一个回文串。
因此中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用”回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
枚举”中心位置”时间复杂度为O(N),从”中心位置”扩散得到”回文子串”的时间复杂度为O(N),因此时间复杂度可以降到O(N²)。
在这里要注意一个细节：回文串在长度为奇数和偶数的时候，”回文中心”的形式是不一样的。
    Ⅰ 奇数回文串的”中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b" ;
    Ⅱ 偶数回文串的”中心”是位于中间的两个字符的”空隙”，例如：回文串 abba 的中心是两个 b 中间的那个”空隙”

代码

package leetcode;

public class D05_03LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        int maxLen = 1;
        String res = s.substring(0, 1);
        for (int i = 0; i < len; i++) {
            String oldStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oldStr.length() > evenStr.length() ? oldStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    private String centerSpread(String s, int left, int right) {
        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);
    }

}

复杂度分析

* 时间复杂度：O(N²)，枚举”中心位置”时间复杂度为O(N),从”中心位置”扩散得到”回文子串”的时间复杂度为O(N),因此时间复杂度可以降到O(N²)。
* 空间复杂度：O(1)，只使用到了常数个临时变量，与字符串长度无关。