LeetCode刷题笔记(五）最长回文子串

心已赠人 2022-05-26 12:10 145阅读 0赞

题目：

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

**示例 1：**

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

**示例2：**

输入: "cbbd"
    输出: "bb"

### 解法1：暴力遍历 ###

class Solution {
        public String longestPalindrome(String s) {
            String result = "";            //最长回文字符串
            int len = s.length();          //字符串长度
    	if(len==1){
    		return s;
    	}
            for(int i = 0;i<len;i++){
                for(int j = i+1;j<len+1;j++){
                    String str = s.substring(i,j);        //截取i-(j-1)的子串
                    if(isPalindrome(str)){
                       result = (j-i)>result.length()?str:result;   //如果这个回文长度大于之前的结果
                    }
                }
            }
            return result;
        }
        //判断是否是回文
        public boolean isPalindrome(String s){
            String perv = new StringBuilder(s.substring(0,(s.length()-1)/2+1)).reverse().toString();      //截取前半段反转，
            return perv.equals(s.substring(s.length()/2,s.length()));            //前半段的反转字符串和后半段是否相等
        }
    }

简单粗暴的方法，依次截取子串，判断是否为回文，再与之前的回文对比长度决定要不要改变最长回文的字符串，这里还可以进行一些优化，比如，1、第二个循环可以从最大值递减，如果得到一个回文符合条件直接break跳出循环，2、对于子串长度的对比可以放在回文判断的前面，这样子可以减少不必要的回文判断，3、截取的子串定义可以放到循环外面，减少重复创建无用的对象。不过即使是这样子，这种方法也没有通过leetcode的监测，结果是超过限制的时间，

时间复杂度：O(n^3)

空间复杂度：O(n^2)

### 2、中间扩展法 ###

class Solution {
        String result = "";
        public String longestPalindrome(String s) {
            int len = s.length();
            for(int i = 0;i<len;i++){
                isPalindrome(s,i,i);        //回文奇数
                isPalindrome(s,i,i+1);      //回文偶数
            }
            return result;
        }
        
        public void isPalindrome(String s,int low,int higth){
            while(low>=0&&higth<s.length()){       //越界检查
                if(s.charAt(low)==s.charAt(higth)){
                    result = ((higth-low+1)>result.length())?s.substring(low,higth+1):result;
                }else{
                    return;
                }
                low--;higth++;
            }
        }
    }

这种算法的原理是：字符串中每一个字符，向两边扩展，得到最长的回文字符串。因为存在回文为偶数和奇数的情况，所以执行了两次不同参数的方法。例如：是奇数：“abcba”,从c向两边扩展2次就得到最长回文字符串“abcba”,但是如果是“abccba”这种情况，从单一的字符串两边扩展无法得到回文。

举个例子：s="ababddbabaca"，先从a开始，得到最长回文“a”,然后从b扩展，得到“aba”,从第三个字符a，得到“bab”，依次进行判断，得出最长的回文字符串。

时间复杂度：O(n^2)

空间复杂度：O(1)

### 3、动态规划法 ###

class Solution {
        public String longestPalindrome(String s) {
           if(s==null||s.length()<2){
               return s;
           }
           int low = 0;              //子串初始索引
           int maxLength = 1;        //子串长度 
           int length = s.length();    //字符串长度
           int[][] flag = new int[length][length];      //如果为1，代表是回文，为0，不是回文
           for(int i = 0;i<length-1;i++){               //初始化flag数组
               flag[i][i] = 1;                          //每一个字符都是回文
               if(s.charAt(i)==s.charAt(i+1)){          //判断每一个字符和后面一个字符是不是回文
                   flag[i][i+1] = 1;
                   low = i;
                   maxLength = 2;
               }
           }
            
           for(int len = 3;len<=length;len++){
               for(int i = 0;i<=length-len;i++){
                   int j = i+len-1;
                   if(flag[i+1][j-1]==1&&s.charAt(i)==s.charAt(j)){       //两边扩展一个字符，判断是不是回文
                        flag[i][j]=1;  
                        maxLength=len;  
                        low=i; 
                   }
               }
           }
            return s.substring(low,maxLength+low);  
        }
    }

动态规划：就是把一个大的条件转换为一个个小的条件，这里要求最长的回文子串，最短的回文子串是1，不过无法构成动态，所以我们先把长度为2的回文子串找出来，flag数组中flag\[i\]\[j\]是标记i-j是否为回文子串，数值为1就是，0就不是。如果s\[i,j\]是回文子串，需要满足两个条件，1、s\[i+1,j-1\]是回文子串，2、s\[i\]=s\[j\]。所以这里是从长度为2的回文子串开始动态改变子串的长度，这里也是向两边扩展，和解法2的有一点类似。

时间复杂度：O(n^2)

空间复杂度：O(n^2)

### 4、Manacher ###

class Solution {
           public String longestPalindrome(String str) {
            // 1.构造新的字符串
            // 为了避免奇数回文和偶数回文的不同处理问题，在原字符串中插入'#'，将所有回文变成奇数回文
            StringBuilder newStr = new StringBuilder();
            newStr.append('#');
            for (int i = 0; i < str.length(); i ++) {
                newStr.append(str.charAt(i));
                newStr.append('#');
            }
    
            // rad[i]表示以i为中心的回文的最大半径，i至少为1，即该字符本身
            int [] rad = new int[newStr.length()];
            // right表示已知的回文中，最右的边界的坐标
            int right = -1;
            // id表示已知的回文中，拥有最右边界的回文的中点坐标
            int id = -1;
            // 2.计算所有的rad
            // 这个算法是O(n)的，因为right只会随着里层while的迭代而增长，不会减少。
            for (int i = 0; i < newStr.length(); i ++) {
                // 2.1.确定一个最小的半径
                int r = 1;
                if (i <= right) {
                    r = Math.min(rad[id] - i + id, rad[2 * id - i]);
                }
                // 2.2.尝试更大的半径
                while (i - r >= 0 && i + r < newStr.length() && newStr.charAt(i - r) == newStr.charAt(i + r)) {
                    r++;
                }
                // 2.3.更新边界和回文中心坐标
                if (i + r - 1> right) {
                    right = i + r - 1;
                    id = i;
                }
                rad[i] = r;
            }
    
            // 3.扫描一遍rad数组，找出最大的半径和索引位置
            int maxLength = 0;
            int index = 0;
            for (int i = 0,len = rad.length;i<len;i++) {
                if (rad[i] > maxLength) {
                    maxLength = rad[i];
                    index = i;
                }
            }
            return newStr.toString().substring(index-maxLength+1,index+maxLength).replace("#","");
        }
    }

这种算法的详细解释有点复杂，它是把字符串的长度都转为奇数，通过添加一个“\#”，然后遍历每一个字符，计算出以这个字符为中心的最长回文子串的长度，把这些长度放入一个数组中，全部求出后，就可以得出最长回文子串了，不过它这里对应算法进行了优化，把一些重复的计算巧妙的根据对称性巧妙的避开了，具体可自行查找Manacher算法的原理，这种方法好像时间复杂度好像更小。

时间复杂度：O(n)；

空间复杂度：O(n)；