最长回文子串Java实现（力扣5/1557）

- 日理万妓 2023-07-14 05:51 11阅读 0赞

力扣刷题小记

**题目描述：**

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

**示例 1：**

**输入: "babad"  
输出: "bab"  
注意: "aba" 也是一个有效答案。  
示例 2：**

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

**来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-substring  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。**

**——————————————————————————————————————————————————————————————————————————————————————————————————————————————————**

**思路一：暴力求解**

对长度为len,len-1,len-2……1 的字符串依次遍历，如果是回文串，则输出。不存在回文串，如“adegv”则以字符串形式输出第一个字符。代码如下：

class Solution {
        public boolean isPalindrome(String s){//检查是否为回文串
            int len=s.length();
            for(int i=0;i<len/2;i++){
                if(s.charAt(i)!=s.charAt(len-1-i))return false;
            }
            return true;
    
        }
        public String longestPalindrome(String s) {
            int start=0,len=s.length();
            if(len==0||len==1)return s;//长度为0或1直接返回字符串本身
            String subStr="";
            for(int i=len;i>1;i--){//以长度递减的方式遍历所有字符串
                for(int j=0;j+i<=len;j++){
                    subStr=s.substring(j,j+i);
                    if(isPalindrome(subStr)==true)return subStr;
                }
            }
            return s.substring(0,1);//不含回文串，返回第一个字符（以字符串形式）
        }
    }

如果回文串判断用递归实现：

class Solution {
        public boolean isPalindrome(String s,int start,int end){//递归实现回文串判断
            if(start>=end)return true;
            if(s.charAt(start)==s.charAt(end))return  isPalindrome(s,start+1,end-1);
            else return false;
        }
        public String longestPalindrome(String s) {
            int start=0,len=s.length();
            if(len==0||len==1)return s;
            String subStr="";
            for(int i=len;i>1;i--){
                for(int j=0;j+i<=len;j++){
                    subStr=s.substring(j,j+i);
                    int subLen=subStr.length();
                    if(isPalindrome(subStr,0,subLen-1)==true)return subStr;
                }
            }
            return s.substring(0,1);
        }
    }

**思路二：动态规划**