【双指针, 中心扩展】最长回文子串

题目

5. 最长回文子串

---

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解题

方法一：暴力(超时)

思路

暴力遍历，把所有字串找出来验证是否回文。

代码

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length(), maxSubLen = 0;
        String ans = "";
        for (int i = 0; i < len; i++) {
            for (int j = i + maxSubLen; j <= len; j++) {
                String subStr = s.substring(i, j);
                if (subStr.equals(new StringBuilder(subStr).reverse().toString())) {
                    maxSubLen = j - i;
                    ans = subStr;
                }
            }
        }
        return ans;
    }
}

方法二：双指针 中心扩展

思路

遍历字符串中每个字符，以字符作中心向两边扩展，扩展的规则为，左右边缘外的两个字符相等，每次扩展到最长时都会和前几次最长的回文子串长度作比较，取最长，最后返回最长的回文子串。

代码

class Solution {
    public int len, start = 0, maxSubLen = 1;

    public String longestPalindrome(String s) {
        len = s.length();
        for (int i = 0; i < len; i++) {
            extend(s, i, i);
            extend(s, i, i + 1);
        }

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

    public void extend(String s, int left, int right) {
        while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        int subLen = right - left - 1;
        if (subLen > maxSubLen) {
            start = left + 1;
            maxSubLen = subLen;
        }
    }
}

优化

在多次要取字符串中字符的情况下，把字符串转为字符数组，取数组中的字符更快，是一种空间换时间的方法。

class Solution {
    private char[] charArr;
    private int n;
    private int begin = 0, maxSubLen = 1;

    public String longestPalindrome(String s) {
        charArr = s.toCharArray();
        n = charArr.length;
        for (int i = 0; i < n; i++) {
            extend(i, i);
            extend(i, i + 1);
        }
        return s.substring(begin, begin + maxSubLen);
    }

    private void extend(int start, int end) {
        while (start >= 0 && end < n && charArr[start] == charArr[end]) {
            start--;
            end++;
        }
        int subLen = end - ++start;
        if (subLen > maxSubLen) {
            maxSubLen = subLen;
            begin = start;
        }
    }
}

class Solution {
    string s;
    int n;
    int max_sub_begin = 0, max_sub_len = 1;

    void extend(int left, int right) {
        while (left >= 0 && right < n && s[left] == s[right]) --left, ++right;
        int len = right - ++left;
        if (len > max_sub_len) {
            max_sub_len = len;
            max_sub_begin = left;
        }
    }

public:
    string longestPalindrome(string _s) {
        s = _s;
        n = s.size();
        for (int i = 0; i < n; ++i) {
            extend(i, i);
            extend(i, i + 1);
        }
        return s.substr(max_sub_begin, max_sub_len);
    }
};