【LeetCode】5. 最长回文子串

链接：

https://leetcode-cn.com/problems/longest-palindromic-substring

描述：

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

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

示例 2：
输入: "cbbd"
输出: "bb"

string longestPalindrome(string s) {}

思路：中心扩散法

枚举回文子串的中心位置，从中心位置尽可能地向两边扩散，得到最长的回文串。

奇偶回文串：

当回文串长度为奇数时，中心位置为一个字符
当回文串长度为偶数时，中心位置为一个空隙，或者可以看作空隙周围的两个字符

枚举中心位置：

在一个字符串中，中心位置可能存在的地方如下图所示。

当最后一个字符为奇数长度的回文串中心时，由于右方无法扩展，所以最大长度为 1 。
这一特例，放入最终结果的初始化中。

其余的，回文串长度为奇数或偶数这两种情况，可以一起循环遍历。
当前字符为第 (i) 个字符：
 回文串长度为奇数时，oddStr = centerSpread(s, i, i)
 回文串长度为偶数时，evenStr = centerSpread(s, i, i + 1)

中心扩散：

设置左右两个指针，两指针中间部分为回文串内容 ((left) , (right))
分别向两边扩散，直到左右指针指向的字符不同，或者溢出边界

C++

展开后查看

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() < 2){
            return s;
        }
        string result = s.substr(0, 1);
        int maxLen = 1;
        for(int i = 0; i < s.size() - 1; i++){
            string oddStr = centerSpread(s, i, i);
            string evenStr = centerSpread(s, i, i + 1);
            string str = oddStr.size() > evenStr.size() ? oddStr : evenStr;
            if(str.size() > maxLen){
                maxLen = str.size();
                result = str;
            }
        }
        return result;
    }
    
    string centerSpread(string s, int left, int right){
        int i = left, j = right;
        while(i >= 0 && j < s.size() && s[i] == s[j]){
            i--;
            j++;
        }
        return s.substr(i + 1, j - i - 1);
    }
};

Java

展开后查看

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2){
            return s;
        }
        String result = s.substring(s.length() - 1, s.length());
        for(int i = 0; i < s.length() - 1; i++){
            String oddStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String str = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if(str.length() > result.length()){
                result = str;
            }
        }
        return result;
    }

    private String centerSpread(String s, int left, int right){
        int i = left, j = right;
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}