【搞定算法】最长回文子串问题

偏执的太偏执、 2021-12-17 01:15 218阅读 0赞

该题目是 LeetCode 上的第五题：[最长回文子串。][Link 1]

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

本文给出该题目的三种解法：**暴力解法、动态规划、Manacher 算法**。暴力解法无法通过运行时间、Manacher 算法有点复杂，所以在真正笔试的时候，我会选择动态规划。但是要是在面试中遇到这道题，可以采用 Manacher 算法进行优化。

> ** 回文子串：**
> 
> 示例 1：
> 
> 输入: "babad"  
> 输出: "bab"  
> 注意: "aba"也是一个有效答案。
> 
> 示例 2：
> 
> 输入: "cbbd"  
> 输出: "bb"
> 
> tips: 回文字符串：正读反读都一样

## 1、暴力解法【基础版本】 ##

最简单的解决方案就是把字符串的所有子串枚举出来，每一个都判断是否是回文字符串，然后选长度最长的回文子串。这种时间复杂度为：O(N^3)，所以通过不了代码运行时间的限制。但是在面试时遇到可以先从简单的说起逐步优化，而且万一想不起来优化，知道暴力解法也好过什么都说不出来，所以，每种题目的暴力解法也是需要练习、总结的（个人见解）。

public class LongestPalindromeSubstring {
    
        public static String getLongestSubStr(String str){
            if(str.isEmpty()){
                return str;
            }
    
            String res = str.substring(0, 1);
            for(int i = 0; i < str.length(); i++){
                for(int j = i + 1; j <= str.length(); j++){
                    String k = str.substring(i, j);
                    // 利用StringBuffer的取反功能
                    String rk = new StringBuffer(k).reverse().toString();
                    if(k.equals(rk) && k.length() > res.length()){
                        res = k;
                    }
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            String str1 = "abcdcba";
            System.out.println(getLongestSubStr(str1));  // bcdcb
        }
    }

## 2、动态规划【笔试版本】 ##

创建一个二维数组 boolean\[\]\[\]dp，其中 dp\[i\]\[j\] 表示字符串第 i 到 j 是否为回文。BaseCase：字符串长度为 1 的都为 true。状态转换如何设定呢？**当字符串 i 所在的字符等于字符串 j 所在的字符，并且它的内部(dp\[i + 1\]\[j - 1\])也为回文，那么 dp\[i\]\[j\] 为 true**。因为这样的规律，我们**要保证判断 dp\[i\]\[j\] 的时候 dp\[i + 1\]\[j - 1\] 已经判断，所以我们遍历采用 i 降序 j 升序的嵌套遍历的方式**。时间复杂度为：O(N^2)。

public class LongestPalindromeSubstring {
    
        public static String getLongestSubStr_DP(String str){
            if(str.isEmpty()){
                return str;
            }
    
            int n = str.length();
            boolean[][] dp = new boolean[n][n];
            int left = 0;
            int right = 0;
            for(int i = n - 2; i >= 0; i--){
                // 单个字符肯定是回文子串
                dp[i][i] = true;
                for(int j = i + 1; j < n; j++){
                    // 当字符串i所在的字符等于字符串j所在的字符，并且它的内部(dp[i+1][j-1])为回文那么dp[i][j]为true
                    // 小于3是因为aba一定是回文
                    dp[i][j] = str.charAt(i) == str.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                    if(dp[i][j] && right - left < j - i){
                        // 记录下回文子串在字符串中的开始和结束位置
                        left = i;
                        right = j;
                    }
                }
            }
            // right必须加1，因为substring方法是左闭右开的
            return str.substring(left, right + 1);
        }
    
        public static void main(String[] args) {
            String str1 = "abcdcba";
            System.out.println(getLongestSubStr(str1));   // abcdcba
        }
    }

贴出 LeetCode 上关于该题目动态规划的讲解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

## 3、Manacher 算法【优化版本】 ##

Manacher 的详细讲解见我的另一篇文章：[Manacher 马拉车算法。][Manacher]

public class Manacher {
    
        public static int maxLcpsLength(String str){
            if(str == null || str.length() == 0){
                return 0;
            }
            // 把字符串处理为manachar类字符串，1221->#1#2#2#1#
            char[] chars = manacherString(str);
            int[] pArr = new int[chars.length];  // 回文半径数组
            int C = -1;  // 取得R时的回文中心
            int R = -1;  //  R-1为最大回文右边界，R是最大回文右边界的下一位
            int max = Integer.MIN_VALUE;
            //遍历每一个字符，计算以该字符为中心的回文字符串长度
            for(int i = 0; i < chars.length; i++){
                //况一： R <= i ,i 彻底在回文右边界的右侧，回文半径至少为 1 （它本身）
                //况二： R > i,
                //得到 i 位置回文半径至少的长度
                pArr[i] = R > i ? Math.min(R - i, pArr[C - (i - C)]) : 1;  // //C-(i-C)即 i'
                //从可能扩得更远的位置开始验证
                while(i + pArr[i] < chars.length && i - pArr[i] > -1){
                    if(chars[i + pArr[i]] == chars[i - pArr[i]]){
                        pArr[i]++;  // 回文半径增大
                    }else{
                        break;   // 已经得到该位置的回文半径了
                    }
                }
                if(i + pArr[i] > R){
                    R = i + pArr[i];
                    C = i;
                }
                // 此回文半径是否比max大，大就替换，否则保持不变不替换。并没有求最大回文字符串是哪一个
                max = Math.max(max, pArr[i]);
            }
            // 返回最大回文字符串长度，因为我们的chars是改造过的，是原字符串的 2倍+1
            // 从中心开始，每个字符后面有一个#，即相当于*2，但中心字符只有一个，所以要-1
            return max - 1;
        }
    
        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;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20211214/3712ed4c854f497090536db6c6f46105.png
[Manacher]: https://blog.csdn.net/pcwl1206/article/details/94876776