LeetCode-5.最长回文子串

本是古典何须时尚 2022-01-31 00:29 224阅读 0赞

# 题目 #

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

###### 示例 1： ######

> 输入: “babad”  
> 输出: “bab”  
> 注意: “aba” 也是一个有效答案。

###### 示例 2： ######

> 输入: “cbbd”  
> 输出: “bb”

解题思路—**中心扩展**：遍历字符串，以每一个字符串都作为中间位，判断是否可以向左右扩展。这里要注意的是，**i 可以作为偶数位回文中心，也可能作为奇数位回文中心**。偶数位回文与奇数位回文的字符串中心是不一样的，所以要**设置两个中心指针left和right**，**如果是奇数位，left=right=i；如果是偶数位，left=i, right=i+1**。

解题思路—**动态规划**：设置一个数组**boolean\[\]\[\] dp**，**dp\[i\]\[j\]的定义为：字符串 i 到 j 是否为回文字符串**。**如果dp\[i\]\[j\]为回文字符串，则dp\[i+1\]\[j-1\]肯定也是回文字符串**。初始化时，**dp\[\]\[\]的对角线都设为true**，因为单个字符本身也可以看作是回文字符串。  
**接下来，i 和 j 如何嵌套是关键问题！！！要保证判断 dp\[i\]\[j\] 前 dp\[i+1\]\[j-1\] 已经判断过了，所以 i+1 到 i ，i 采用升序遍历；j 到 j-1，j 采用降序遍历。同时要注意，i < j，这个条件一定要满足！**

✨✨解题思路—**Manacher算法**：Manacher算法是一种解决最长回文子串问题的巧妙解法，就是过程不太容易理解，**详细解释可以看这篇—[Manacher算法解决最长回文子串问题][Manacher]，配合图解理解更快！这个方法非常推荐！！！！！**

## Java解题—中心扩展 ##

class Solution {
        public String longestPalindrome(String s) {
            if(s==null || s.length()==0)
                return "";
    
            int start = 0, end = 0;
            for(int i=0;i<s.length();i++){
                int len1 = expandString(s, i, i); // 奇数
                int len2 = expandString(s, i, i+1); // 偶数
                int len = Math.max(len1, len2);
                if(len>end-start+1){
                    start = i - (len-1)/2;
                    end = start + len -1;
                }
            }
            return s.substring(start, end+1);
        }
        
        public static int expandString(String s, int left, int right){
            int l = left, r = right;
            while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
                l--;
                r++;
            }
            return r-l-1;
        }
    }

## Java解题—动态规划 ##

class Solution {
        public String longestPalindrome(String s) {
            if(s==null || s.length()==0)
                return "";
    
            char[] ss = s.toCharArray();
            boolean[][] dp = new boolean[ss.length][ss.length];
            int left = 0, right = 0;
            for(int j=0;j<ss.length;j++){
                dp[j][j] = true; // s[i]本身就是回文字符串
                for(int i=j-1;i>=0;i--){
                    if(ss[j]==ss[i] && (j-i<3 || dp[i+1][j-1])) // j-i<3 即字符串长度为3，在ss[j]==ss[i]成立的情况下，一定是回文字符串
                        dp[i][j] = true;
                    if(dp[i][j] && right-left<j-i){
                        right = j;
                        left = i;
                    }
                }
            }
            return s.substring(left, right+1);
        }
    }

## Java解题—Manacher算法 ##

class Solution {
        public String longestPalindrome(String s) {
            if(s==null || s.length()==0)
                return "";
            
            int[] max = maxLcpsLength(s);
            StringBuilder str = new StringBuilder();
            while(max[1]-->0)
                str.append(s.charAt(max[0]++));
            return str.toString();
        }
        
        // 处理字符串
        public static char[] manacherString(String str){
            char[] chars = str.toCharArray();
            char[] res = new char[chars.length*2+1];
            int index = 0;
            for(int i=0;i<res.length;i++)
                // 偶数位加 # ，奇数位不变
                res[i] = (i&1)==0?'#':chars[index++];
            return res;
        }
    
        // 马拉车算法
        public static int[] maxLcpsLength(String str){
            char[] chars = manacherString(str);
            int[] len = new int[chars.length]; // 记录每个回文字符串的长度
            int right = -1; // 当前回文的右边界
            int cen = -1; // 当前回文的中心
            int[] max = {-1, -1}; // 记录回文的最大值
            for(int i=0;i<chars.length;i++){
                // 2*cen-i是i点关于cen的对称点
                // right>i时，Math.min(len[2*cen-i], right-i),两种情况取最小，往外扩
                // right<=i时，以i为中心的回文没有被访问过，所以当前回文字符串只有i，len[i]=1
                len[i] = right>i? Math.min(len[2*cen-i], right-i) : 1;
                // 以i为中心，左右扩
                while(i-len[i]>-1 && i+len[i]<chars.length){
                    if(chars[i-len[i]]==chars[i+len[i]])
                        len[i]++; // 左右字符相等，符合回文，len++；
                    else
                        break;
                }
                // 更新当前回文的右边界以及中心
                if(i+len[i]>right){
                    right = i + len[i];
                    cen = i;
                }
                if(max[1]<len[i]-1){
                    max[0] = (i-1)/2 - (len[i]-2)/2;
                    max[1] = len[i]-1;
                }
            }
            return max;
        }
    }

[Manacher]: https://blog.csdn.net/gaoyueace/article/details/90217098