LeetCode刷题第5题:最长回文子串

原文链接：https://leetcode.cn/problems/longest-palindromic-substring/

题意

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

示例

示例1：

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

示例2：

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

解题

解题思路

• 直接法（推荐）

class Solution {
   public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        char[] ss = s.toCharArray();
        int start =0;
        int end =0;
        for(int i = 0; i<ss.length; i++){
            int len0 = subStringLong(ss,i,i);
            int len1 = subStringLong(ss,i,i+1);
            int len = len0>len1 ? len0:len1;
            if(end - start < len) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start,end+1);
    }
    public int subStringLong(char[] s,int left,int right){
        while(left>=0 && right<s.length && s[left]==s[right]){
            left--;
            right++;
        }
        return right-left-1;
    }
}

• 马拉车算法实现最长回文子串

class Solution {
 // 马拉车算法实现最长回文子串
    public static String longestPalindrome(String s) {
        // 对空字符串或单字符字符串直接返回原字符串
        if (s.length() == 0 || s.length() == 1)
            return s;

        // 构建一个新的字符串，其中每个原始字符之间插入特殊字符（如'#'）
        // 这样做是为了统一处理奇数长度和偶数长度的回文串
        StringBuilder temp = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            temp.append(s.charAt(i)).append("#");
        }

        // 新字符串的长度
        int n = temp.length();
        // p数组，p[j] 表示以字符j为中心的最长回文半径
        int[] p = new int[n];

        // id是最长回文子串中心的位置，mx是以id为中心的回文子串能到达的最右端的位置
        int id = 0, mx = 0;
        // 记录最长回文子串的长度和中心位置
        int maxLength = -1;
        int index = 0;

        // 遍历新字符串
        for (int j = 1; j < n - 1; j++) {
            // 利用已知回文信息初始化p[j]
            p[j] = mx > j ? Math.min(p[2 * id - j], mx - j) : 1;

            // 中心扩展，检查并更新p[j]
            while (j + p[j] < n && j - p[j] >= 0 && temp.charAt(j + p[j]) == temp.charAt(j - p[j])) 			{
                p[j]++;
            }

            // 更新id和mx
            if (mx < j + p[j]) {
                mx = j + p[j];
                id = j;
            }

            // 更新最长回文子串的信息
            if (maxLength < p[j] - 1) {
                maxLength = p[j] - 1;
                index = j;
            }
        }
        // 计算原始字符串中最长回文子串的起始位置
        // (index - maxLength) / 2 是在添加了特殊字符的字符串中的起始位置
        int start = (index - maxLength) / 2;

        // 返回原始字符串中的最长回文子串
        return s.substring(start, start + maxLength);
    }
}

• 字符串与本身反转后比较

class Solution {
    public String longestPalindrome(String s) {
		//字符串长度
        int length = s.length();
        //初始化最长回文串
        String maxStr="";
        //将字符串进行反转：dabab
        String reverse=new StringBuffer(s).reverse().toString();
		
        int x=0,y=1; //初始化字符下标
        
        /*s="babad"，
        *比如：babad ->dabab（s反转）
        *判断截取范围是否超出s字符串的长度
        *截取范围内的字符串在s反转字符串是否存在
        （存在：获取该最长回文子串；不存在：初始下标进行移位）
        *获取该最长回文子串的方式：需判断该截取的字符串与本身反转字符是否相等
        *若相等（更新最长回文串），
        需判断当前截取范围内的字符串与上一次回文字符串比较，长度最长的作为最长回文串
        *最后，需最右侧游标进行移动后一位
        */
        //临界条件
        while (x<length&&y<=length){
            //截取部分字符串
            String substring = s.substring(x, y);
            //截取的部分字符串在反转字符串中是否能够找到
            if (reverse.contains(substring)){
                //判断截取的部分字符串与它本身反转后的字符串是否相等
                if(substring.equals(new StringBuffer(substring).reverse().toString()))
                    //获取最长回文字符串
                    if (substring.length()>maxStr.length()){
                        maxStr=substring;
                    }
                y++;
            }else { //截取的部分字符串在反转字符串中未找到，则进行移位
                x++;
                y=x+1;
            }
        }
        return maxStr;
    }
}