【leetcode】第5题：最长回文子串

Bertha 。 2022-02-22 15:50 203阅读 0赞

## **目  录:** ##

**一、暴力解法**

**二、动态规划**

**三、中心扩展法**

**四、Manacher 算法**

--------------------

先说明几个概念：

> 1. **子串**：小于等于原字符串长度，由原字符串中任意个**连续**字符组成的子序列；
> 
> 2. **回文**：关于中间字符对称的字符串，例如："ababa"（单核）、"abccba"（双核）；
> 
> 3. **最长回文子串**：回文子串中最长的子串。

## 一、暴力解法【时间复杂度：O(![n^\{3\}][n_3])】 ##

*   基本思路：遍历该字符串所有的子串，找出其中是回文子串且长度最长的那个。所以，我们可以倒着遍历该字符串，从最长的子串开始，这样只用找到第一个是回文字符串就可以了，它一定是原字符串最长的回文子串。

> 1、 从最长的子串开始，遍历该字符串的所有子串（时间复杂度为：O(n^2)）；
> 
> 2、判断当前子串是否为回文串（时间复杂度为：O(n)）；
> 
> 3、当前子串为回文时，则找到了原字符串的最长回文子串，结束遍历；否则，继续遍历，直到遍历完所有子串。

*  代码实现

public class LongestPalindrome_5 {
    
        public static void main(String[] args) {
    
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            getLongestPalindrome1(str);
        }
    
        // 暴力解法
        public static String getLongestPalindrome1(String str){
            if(str.length() <= 1){
                return str;
            }
    
            // 前两层循环是求字符串的所有子串
            for(int i = str.length(); i > 0; i--){
                for(int j = 0; j <= str.length() - i; j++){
                    String sub = str.substring(j, i + j);
                    int count = 0;
                    // 检验当前的子串是否为回文串
                    for(int k = 0; k < sub.length() / 2; k++){
                        // k是从0开始的，所以是sub.length-k-1
                        if(sub.charAt(k) == sub.charAt(sub.length() - k - 1)){
                            count++;
                        }
                    }
                    if(count == sub.length() / 2){
                        System.out.println(sub);
                        return sub;
                    }
                }
            }
            return "";  // 没有
        }
    }

*  从分析和代码实现上，可以很明显的看出，暴力解法的时间复杂度是：O(n^3)，无论是笔试还是面试显然都是不行的。

--------------------

## 二、动态规划【时间复杂度：O(![n^\{2\}][n_2])】 ##

回文字符串的子串也是回文，比如P\[i, j\]（表示以 i 开始，以 j 结束的子串）是回文字符串，那么P\[i+1, j-1\]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O（N^2)，算法复杂度也是O(N^2)。

*  首先定义状态方程和转移方程：

> P\[i, j\] = false：表示子串\[i, j\]不是回文串；P\[i, j\] = true：表示子串\[i, j\]是回文串。
> 
> P\[i, i\] = true：当且仅当P\[i+1, j-1\] = true && (s\[i\] == s\[j\]）否则p\[i,j\] =false;

public class LongestPalindrome_5 {
    
        public static void main(String[] args) {
    
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            String subStr = getLongestPalindrome3(str);
            System.out.println(subStr);
        }
    
        // 动态规划
        public static String getLongestPalindrome2(String str){
            if(str == null && str.length() <= 0){
                return "";
            }
    
            int len = str.length();
            int start = 0;            // 记录字符串起始的位置
            int maxLength = 1;        // 记录回文串的最大长度
            boolean dp[][] = new boolean[str.length()][str.length()];
    
            // 长度为1和2的子串的初始化
            for(int i = 0; i < len; i++){
                // 初始化所有长度为1的子串
                dp[i][i] = true;
                // 初始化所有长度为2的子串
                if(i < len - 1 && str.charAt(i) == str.charAt(i + 1)){
                    dp[i][i + 1] = true;
                    start = i;
                    maxLength = 2;
                }
            }
    
            // 以字符串长度为1和2的子串为基础，推导长度：3~len 的子串的dp
            for(int strlen = 3; strlen <= len; strlen++){
                // 从头开始，遍历长度为strlen的子串，并判断它们是否为回文串
                for(int i = 0; i <= len - strlen; i++){
                    int j = i + strlen - 1;   // 子串结束位置的下标
                    if(dp[i + 1][j - 1] && str.charAt(i) == str.charAt(j)){
                        dp[i][j] = true;
                        // 更新最大回文子串长度为当前子串长度，因为子串长度是不断增加的，所以最后一个回文串肯定是最长的
                        maxLength = strlen;
                        start = i;  // 记录回文串开始位置的下标
                    }
                }
            }
    
            if(maxLength > 0){
                return str.substring(start, start + maxLength);
            }
            return "";
        }
    }

--------------------

## 三、中心扩展法【时间复杂度：O(![n^\{2\}][n_2])】 ##

事实上，只需使用恒定的空间，我们就可以在 O(n^2) 的时间内解决这个问题。

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n −1 个这样的中心。

你可能会问，为什么会是 2n - 1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 \{“abba”\}的中心在两个\{‘b’\}之间）。【和在两个字符之间添加“\#”是一个道理】

public class LongestPalindrome_5 {
    
        public static void main(String[] args) {
    
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            String subStr = getLongestPalindrome3(str);
            System.out.println(subStr);
        }
    
        // 中心扩展法
        public static String getLongestPalindrome3(String str){
            if(str == null && str.length() <= 0){
                return "";
            }
    
            int maxLength = 1;
            int start = 0;
    
            // 类似于aba这种情况，以i为中心向两边扩展
            for(int i = 0; i < str.length(); i++){
                int j = i - 1;
                int k = i + 1;
                while((j >= 0 && k < str.length()) && str.charAt(j) == str.charAt(k)){
                    if(k - j + 1 > maxLength){
                        maxLength = k - j + 1;
                        start = j;
                    }
                    j--;
                    k++;
                }
            }
    
            // 类似于abba这种情况，以i，i+1为中心向两边扩展
            for(int i = 0; i < str.length(); i++){
                int j = i;
                int k = i + 1;
                while((j >= 0 && k < str.length()) && str.charAt(j) == str.charAt(k)){
                    if(k - j + 1 > maxLength){
                        maxLength = k - j + 1;
                        start = j;
                    }
                    j--;
                    k++;
                }
            }
            if(maxLength > 0){
                return str.substring(start, start + maxLength);
            }
            return "";
        }
    }

*  可以看到上面代码非常长，可以发现主要就是奇回文和偶回文两种情况的处理，代码高度一致。可以精简下，这里贴出 leetcode 官方提供的代码。
 *  其实对于笔试来说，通过最重要，还是推荐上面的代码，虽然长，但是思路比较清晰。

--------------------

## 四、Manacher 算法 ##

后续补上.......

[n_3]: https://private.codecogs.com/gif.latex?n%5E%7B3%7D
[n_2]: https://private.codecogs.com/gif.latex?n%5E%7B2%7D