【LeetCode: 5. 最长回文子串 | 暴力递归=＞记忆化搜索=＞动态规划 =＞ 中心扩展法】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 5. 最长回文子串

⛲ 题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

🌟 求解思路&实现代码&运行结果

⚡ 暴力递归

🥦 求解思路

1. 这道题目非常高频，而且解决的方法相对来说也比较多，成熟的一些方法也非常多，接下来我来分享一下我的求解思路。
2. 判断回文串的首要思路有俩种，一种是从中心开始，另外一种就是从俩边向中心判断，我们首先采取的就是第二种方法，我们暴力枚举每一个区间，然后判断该区间是否是回文串，并且长度大于之前回文串的结果，我们直接记录并返回。

🥦 实现代码

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<0||s==null) return null;
        char[] arr=s.toCharArray();
        int n=arr.length;
        String ans = "";
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if(process(i,j,arr)&&j-i+1>ans.length()){
                    ans=s.substring(i,j+1);
                }
            }
        }
        return ans;
    }

    public boolean process(int left,int right,char[] arr){
        if(left==right) return true;
        if(left+1==right) return arr[left]==arr[right];
        boolean flag=false;
        if(arr[left]==arr[right]){
            flag|=process(left+1,right-1,arr);
        }
        return flag;
    }
}

🥦 运行结果

时间居然没有超，但是这时间复杂度也太慢了，为了让各位看官大爷有更好的体验，我们还是继续优化。使用我们的锦囊妙计！

⚡ 记忆化搜索

🥦 求解思路

1. 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。

🥦 实现代码

class Solution {
    int[][] dp;
    public String longestPalindrome(String s) {
        if(s.length()<0||s==null) return null;
        char[] arr=s.toCharArray();
        int n=arr.length;
        dp=new int[n][n];
        for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);
        String ans = "";
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if(process(i,j,arr)&&j-i+1>ans.length()){
                    ans=s.substring(i,j+1);
                }
            }
        }
        return ans;
    }

    public boolean process(int left,int right,char[] arr){
        if(left==right) return true;
        if(left+1==right){
            dp[left][right]=arr[left]==arr[right]?1:0;
            return arr[left]==arr[right];
        }
        if(dp[left][right]!=-1) return dp[left][right]==1;
        boolean flag=false;
        if(arr[left]==arr[right]){
            flag|=process(left+1,right-1,arr);
        }
        dp[left][right]=flag?1:0;
        return flag;
    }
}

🥦 运行结果

傻缓存也还不错！

⚡ 动态规划

🥦 求解思路

1. 按照我们之前递归和记忆化搜索的思路，通过动态规划实现出来。

🥦 实现代码

class Solution {
    boolean[][] dp;
    public String longestPalindrome(String s) {
        if(s.length()<0||s==null) return null;
        char[] arr=s.toCharArray();
        int n=arr.length;
        dp=new boolean[n+1][n+1];
        String ans = "";
        for(int left=n-1;left>=0;left--){
            for(int right=left;right<n;right++){
                boolean flag=false;
                if(left==right){
                    dp[left][right]=true; 
                    flag|=true;
                }
                else if(left+1==right){
                    dp[left][right]=arr[left]==arr[right];
                    flag|=dp[left][right];
                }else{
                    if(arr[left]==arr[right]){
                        flag|=dp[left+1][right-1];
                    }
                }
                dp[left][right]=flag;
                if(flag&&right-left+1>ans.length()){
                    ans=s.substring(left,right+1);
                }
            }
        }
        return ans;
    }
}

🥦 运行结果

⚡ 中心扩展法

🥦 求解思路

1. 我们可以考虑以每一个位置为中心，向左右位置进行扩展，如果相等，左右指针继续移动，找到该位置最长的回文子串。
2. 因为我们的回文子串可能为奇数，也可能为偶数，我们可以调用俩次扩展的方法，从i,i 以及i,i+1位置开始，遍历所有结果，找到最长的即可。
3. 扩展方法我设计的是返回一个数组，res[0]是最长回文子串的开始位置，res[1]是最长回文子串的长度。

🥦 实现代码

class Solution {

    public String longestPalindrome (String A) {
        // write code here
        int len=0;
        int[] res=new int[2];
        for(int i=0;i<A.length();i++){
            int[] res1=process(A,i,i);
            int[] res2=process(A,i,i+1);
            int[] max=res1[1]>res2[1]?res1:res2;
            if(max[1]>len){
                res=max;
                len=res[1];
            }
        }
        return A.substring(res[0],res[0]+res[1]);
    }
     
    public int[] process(String str,int i,int j){
        while(i>=0&&j<str.length()&&str.charAt(i)==str.charAt(j)){
            i--;
            j++;
        }
        return new int[]{i+1,j-i-1};
    }
}

🥦 运行结果

💬 共勉