最长的回文子串_

小菜鸟

/**思路：
* 从回文串的对称点开始，依次向左向右比较，不相同的时候停止遍历，直到找出最大的长度的回文子串。
*    （1）回文子串长度为奇数：对称点只有一个字符
*    （2）回文子串长度为偶数：对称点有两个字符
* 时间复杂度为O(n^2):对称点的数量为O(n),每次查找的时间也为O(n),所有总时间复杂度为O(n^2) */

class Solution {
public:
    string longestPalindrome(string s) {
        //字符串的长度
        int len = s.size();
        if (len == 0) return s;
        //保留最长回文串
        string resultStr = "";
        //回文子串长度为奇数,：对称点只有一个字符的情况
        for (int i=0; i<len; ++i){
            // i 为对称点
            int left = i;//左
            int right = i;//右
            //向左向右遍历，直到发现不相同的时候停止
            while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){
                --left;
                ++right;
            }
            //比较，更新最长回文串
            if (right - left + 1 > resultStr.size()){
                resultStr = s.substr(left, right - left + 1);
            }
        }
        
        //回文子串长度为偶数：对称点有两个字符
        for (int i = 0; i < len - 1; ++i){
            if (s[i] == s[i+1]){//两个对称点相同，才有继续遍历的意义
                int left = i;
                int right = i+1;
                //向左向右遍历，直到发现不相同的时候停止
            	while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){
               		--left;
                	++right;
            	}
            	//比较，更新最长回文串
            	if (right - left + 1 > resultStr.size()){
                	resultStr = s.substr(left, right - left + 1);
            	}
            }
        }
        return resultStr;
    }
};

发表于 2016-06-07 16:02:46 回复(3)

BugFree

思路一：中心扩展法：就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。但是要考虑两种情况：1、像aba，这样长度为奇数。2、像abba，这样长度为偶数。

思路二：DP 思路：P[i][j]是记录i到j子串是不是回文串。P(i,j)={true,if the substring Si…Sj is a palindrome;false,if the substring Si…Sj is not a palindrome}。那么可以得到：

P(i,j)=(P(i+1,j−1) && Si==Sj)

思路三：Manacher's Algorithm俗称马拉车算法，复杂度可以达到O(n)

详见：http://blog.csdn.net/u011489043/article/details/70303132

欢迎各位关注在下的微信公众号“张氏文画”，不光有新鲜的 LeetCode 题解，还有经典的文章及短视频和大家分享，一起嘿嘿嘿

编辑于 2020-03-26 16:07:28 回复(0)

C/C++

努力的牛牛

    /*
    * 目的：求最大回文子串
    * 方法：动态规划
    */
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>>dp(n,vector<bool>(n,false));
        int maxVal = 1;
        int pos[2]={0,0};
        for (int j = 0; j< s.size();++j){
            dp[j][j] = true;
            for (int i = 0;i<j;++i)
            {
                dp[i][j] = (s[i]==s[j] &&(j-i<=2 || dp[i+1][j-1]));
                if(dp[i][j] && (j-i+1 > maxVal))
                  {
                      pos[0] = i;
                      pos[1] = j;
                      maxVal = j-i+1;
                  }
            }
        }
        return s.substr(pos[0],pos[1]-pos[0]+1);
    }

发表于 2019-12-11 19:53:15 回复(0)

风中追风20180314092925

思路：
动态规划
如果只是求最长回文子串的长度，其递推公式与 "最长回文子序列" 完全相同

这里需要给出具体的子串，需要重新定义 dp

定义：
    dp[i][j] := 子串 s[i..j] 是否是回文子串
初始化
    dp[i][j] = true     i=j
              = false    other
递推公式：
dp[i][j] = s[i]==s[j]                   j-i=1
          = s[i]==s[j]&&dp[i+1][j-1]      j-i>1


	string longestPalindrome(string s) {



	    int n = s.length();



	    vector<vector<int>> dp(n, vector<int>(n, 0));      



	    //用下标来记录,防止出现单一回文情况 



	    int max_len = 1;    //保存最长回文子串长度 



	    int start = 0;      //保存最长回文子串起点 



	    for (int i = 0; i < n; i++)



	        dp[i][i] = 1;



	     



	    for (int j = 1; j < n; j++)             // 子串结束位置 



	        for (int i = j - 1; i >= 0; i--) {  // 子串开始位置 



	            if (j - i < 2)



	                dp[i][j] = (s[i] == s[j]);



	            else 



	                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);              



	            // 保存子串 



	            if (dp[i][j] && (j - i + 1) >= max_len) {



	                max_len = j - i + 1;



	                start = i;



	            }



	        }



	    return s.substr(start, max_len);



	}

刚开始的想法是直接DFS，但会超时，也记录一下吧


	bool isPalindrome1(string s){



	    return s == string(s.rbegin(), s.rend());



	}



	void dfsPalindrome(string s, string &res){



	    if(s == "")



	        return ;



	    for (int i = 1; i <= s.size(); ++i) {



	        string temp = s.substr(0, i);



	        if(isPalindrome1(temp)){



	            if(temp.size() > res.size())



	                res = temp;



	            dfsPalindrome(s.substr(i), res);



	        }



	    }



	}



	string longestPalindrome(string s) {



	    string res;



	    dfsPalindrome(s, res); 



	    return res;



	}

更详细的解释或细节不懂的博客留言：https://blog.csdn.net/qq_43208303/article/details/89672406

编辑于 2019-04-29 12:49:28 回复(0)

W.sl

//复杂度应该是o(n)吧
public class Solution {
    public String longestPalindrome(String s) {
        
        int[] p;
        StringBuilder sb = new StringBuilder();
	sb.append('$');
	sb.append('#');
	for(int i=0;i<s.length();i++){
		sb.append(s.charAt(i));
		sb.append('#');
	}
	int mx=0;
	int ans=0;
	int id=0;
	p=new int[sb.length()];
	for(int i=1;i<sb.length();i++){
				
		if(mx>i){
			p[i]=Math.min(p[2*id-i], mx-i);
		}else
			p[i]=1;
		while(i+p[i]<sb.length()&&i-p[i]>=0&&sb.charAt(i-p[i])==sb.charAt(i+p[i])){
			p[i]++;
		}
		if(p[i]+i>mx){
			id=i;
			mx=p[i]+i;
		}
		ans = Math.max(ans, p[i]);
		}
        int max=0;
	int k=0;
	for(int i=0;i<p.length;i++){
				
		if(p[i]>max){
			k=i;
			max=p[i];
		}
	}
        StringBuilder sb1= new StringBuilder();
        for(int i=k-max+1;i<k+max-1;i++){
				
		if(sb.charAt(i)!='#'&&sb.charAt(i)!='$'){
			sb1.append(sb.charAt(i));
		}
	}
	return sb1.toString();
    }
}

发表于 2016-10-19 16:31:51 回复(0)

promethus

//中心扩散
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n <= 1) return s;
        int start = 0, maxlen = 0;
        for(int i = 1; i < n; ++i)
        {
            //寻找以i-1,i为中点偶数长度的回文
            int low = i-1, high = i;
            while(low >= 0 && high < n && s[low] == s[high])
            {
                low --;
                high ++;
            }
            if(high - low - 1 > maxlen)
            {
                maxlen = high - low - 1;
                start = low + 1;
            }

            //寻找以i为中心的奇数长度的回文
            low = i-1, high = i+1;
            while(low >=0 && high < n && s[low] == s[high])
            {
                low --;
                high ++;
            }
            if(high - low - 1 > maxlen)
            {
                maxlen = high - low - 1;
                start = low + 1;
            }
        }
        return s.substr(start, maxlen);
    }
};

// dp记录子串是否是回文串
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n <= 1) return s;
        vector<vector<int>> dp(n, vector<int>(n,0));
        int start = 0, ends = 1;
        for(int i = 0; i < n; ++i)
        {
            dp[i][i] = 1;    // 一个字母的情况
            if(s[i] == s[i+1] && i != n-1)  // 两个字母相等的情况
            {
                dp[i][i+1] = 1;
                start = i;
                ends = 2;
            }
        }
        for(int i = 3; i <= n; ++i)  // 子串的长度
        {
            for(int j = 0; j + i - 1 < n; ++j)
            {
                int k = j + i -1;
                if(s[j] == s[k] && dp[j+1][k-1] == 1)
                {
                    dp[j][k] = 1;
                    start = j;
                    ends = i;
                }
            }
        }
        return s.substr(start,ends);
    }
};

发表于 2019-10-06 21:55:36 回复(0)

llch__

    public String longestPalindrome(String s) {
        int maxlength = 0;
        int start = 0;
        int end = 1;
        for(int i=0; i<s.length(); i++){
            for(int j=0; j<2; j++){ //以i为中心的情况，和以i, i+1为中心的情况
                int left = i;   
                int right = i+j;
                if(right == s.length()) break;
                while(left >= 0 && right <s.length() && s.charAt(left) == s.charAt(right)){
                    left--;
                    right++;
                }
                left ++;
                if(maxlength < right - left){
                    maxlength = right-left;
                    start = left;
                    end = right;
                }
            }
        }
        return s.substring(start, end);
    }

发表于 2018-08-03 21:30:30 回复(1)

c++好难

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool> >dp(s.length(),vector<bool>(s.length(),false));
        int left=0,right=0;
        for(int i=0;i<s.length();++i){
            for(int j=i;j>=0;--j){
                if(s[i]==s[j] && (i-j<2 || dp[j+1][i-1]==true)){
                    dp[j][i]=true;
                    if(i-j>right-left){
                        left=j;
                        right=i;
                    }
                }
            }
        }
        return s.substr(left,right-left+1);
    }
};

发表于 2018-06-26 08:27:43 回复(1)

一个菜鸡的自我修养

//利用马拉车算法进行求解
//有关动态规划，中心扩散法，以及马拉车算法的理解可参考我的博客
//http://www.cnblogs.com/pathjh/p/8798277.html
import java.util.*;
public class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<2) 
            return s;
     int[]p;
        StringBuilder sb=new StringBuilder();
        //对字符串进行预处理
        sb.append('$');
        sb.append('#');
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            sb.append('#');
        }
        p=new int[sb.length()];
        int mx=0,id=0;
        int resLen=0,resCenter=0;
        for(int i=1;i<sb.length();i++){
            p[i]=i<mx?Math.min(p[2*id-i],mx-i):1;
            while(i+p[i]<sb.length()&&i-p[i]>=0&&sb.charAt(i+p[i])==sb.charAt(i-p[i]))
                p[i]++;
            if(mx<i+p[i]){
                mx=i+p[i];
                id=i;
            }
            if(resLen<p[i]){
                resLen=p[i];
                resCenter=i;
            }
        }
        //一趟循环下来后，此时resLen对应的为最长的回文子串的半径长度，resCenter对应的是最长回文子串的中心位置
        StringBuilder sb1=new StringBuilder();
        for(int i=resCenter-resLen+1;i<=resCenter+resLen-1;i++){
            if(sb.charAt(i)!='#'&&sb.charAt(i)!='$')
                sb1.append(sb.charAt(i));
        }
        return sb1.toString();
    }
}

发表于 2018-05-13 23:09:57 回复(0)

C/C++

nbgao

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<=1)
        	return s;
        int min_s = 0, max_l = 1;
        int n = s.length();
        for(int i=0;i<n;)
        {
        	if(n-i <= max_l/2)
        		break;
        	int j=i,k=i;
        	while(k<n-1 && s[k]==s[k+1])
        		k++;
        	i = k+1;
        	while(j>0 && k<n-1 && s[j-1]==s[k+1])
        	{
        		k++;
        		j--;
			}
			int new_l = k-j+1;
			if(new_l > max_l)
			{
				max_l = new_l;
				min_s = j;
			}						 
		}
		return s.substr(min_s,max_l);
    }
};

发表于 2017-09-11 01:22:38 回复(0)

已注销

//大家好，我是yishuihan
public class Solution {
   public String longestPalindrome(String s){
	int maxLeft=0;
	int maxRight=0;
	int max=1;
	int n=s.length();
	for(int i=0;i<n;i++)
	{
		//偶数长度的回文子串
		int start=i;
		int end=i+1;
		int len=0;
		//left、right是为了防止越界
		int left=start;
		int right=end;
		while(start>=0&&end<n)
		{
			if(s.charAt(start)==s.charAt(end))
             {
				len=len+2;
				left=start;
				right=end;
				start--;
				end++;
			  }
             else
				break;
		}
		if(len>max){
			maxLeft=left;
			maxRight=right;
			max=len;
		}
		//奇数长度的回文子串
		start=i-1;
		end=i+1;
		len=1;
		left=start;
		right=end;
		while(start>=0&&end<n){
			if(s.charAt(start)==s.charAt(end))
			{
				len=len+2;
				left=start;
				right=end;
				start--;
				end++;
			}
			else
				break;
		}
		if(len>max){
			maxLeft=left;
			maxRight=right;
			max=len;
		}
	}
	return s.substring(maxLeft, maxRight+1);
}
}

发表于 2016-08-06 20:18:05 回复(0)

JacobGo！

/*
 * 感觉是最优解了，还有更好的解法求告知
 */
private int left, maxLen;
	public String longestPalindrome(String s) {
		if (s == null || s.length() < 2)
			return s;
		for (int i = 0; i < s.length() - 1; i++) {
			//考虑两种情况：1.中间是bab;2.中间是bb;
			findMaxPalindrome(s, i, i);
			findMaxPalindrome(s, i, i + 1);

		}

		return s.substring(left, left + maxLen);
	}

	private void findMaxPalindrome(String s, int i, int j) {
		while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
			
			i--;
			j++;
		}
		if (maxLen < j - i - 1) {
			left = i+1;
			maxLen = j - i - 1;
		}
	}

发表于 2017-07-05 10:43:49 回复(11)

LinuX18

class Solution {
public:
    // 最长回文串，使用dp
    string longestPalindrome(string str) 
    {
     int n = str.length();
    if(n==0) return "";
    bool dp[n][n];
    fill_n(&dp[0][0],n*n,false);
    int left=0,right=0,maxLen = 0;
    for(int j=0;j<n;j++)
    {
      dp[j][j] = true;
      for(int i=0;i<j;i++)
      {
          dp[i][j] = (str[i] == str[j] && (j-i < 2 || dp[i+1][j-1]));
          if(dp[i][j] && (j-i+1 > maxLen))
          {
              left = i;
              right = j;
              maxLen = j-i+1;
          }
      }
    }
    return str.substr(left,right-left+1);
    }
};

发表于 2017-07-10 23:02:41 回复(5)

C++

dalyk

class Solution {
public:
/**
*
* @param s string字符串
* @return string字符串
*/
string longestPalindrome(string s) {
// write code here
int max_left=0,max_right=-1;
for(int i=0;i<s.size();i++){
int left=i,right=i;
while(left>=0&&s[left]==s[i])left--;
while(right<s.size()&&s[i]==s[right])right++;
while(left>=0&&right<s.size()&&s[left]==s[right])
left--,right++;
if(max_right-max_left<right-left)
max_left=left,max_right=right;

}
return s.substr(max_left+1,max_right-max_left-1);
}
};

发表于 2021-09-19 10:52:32 回复(0)

Java

SnailLLL

//中心拓展法
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String longestPalindrome (String s) {
        // write code here
        if(s==null || s.length()==0) return s;
        int index=0;
        int max=0;
        for(int i=0;i<s.length();i++){
            if(max<maxLengthOfPalindrome(s,i,i)){
                index=i;
                max=maxLengthOfPalindrome(s,i,i);
            }
            if(max<maxLengthOfPalindrome(s,i,i+1)){
                index=i;
                max=maxLengthOfPalindrome(s,i,i+1);
            }
        }
        if(max%2==1) return s.substring(index-max/2,index-max/2+max);
        else return s.substring(index+1-max/2,index+1+max/2);
    }
    private int maxLengthOfPalindrome(String s, int i, int j){
        int res=(i==j)?-1:0;
        while(i>=0 && j<s.length()){
            if(s.charAt(i)==s.charAt(j)){
                res+=2;
                i--;
                j++;
            }else{
                break;
            }
        }
        return res;
    }
}

发表于 2021-06-02 12:20:05 回复(0)

大风起，野猪飞O(∩_∩)O

解决思路

把输入取逆序，然后和原输入求最长子序列。

public class Solution {
    public static String longestPalindrome (String s) {
        int n = s.length();
        char[] a = s.toCharArray();
        char[] b = new char[n];
        for (int i = 0; i < n; i++)
            b[i] = a[n - i - 1];
        int[][] ans = new int[n + 1][n + 1];
        for (int i = 0; i < n + 1; i++) {
            ans[0][i] = 0;
            ans[i][0] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[i + 1][j + 1] = b[i] == a[j] ? ans[i][j] + 1 :
                        Math.max(ans[i][j + 1], ans[i + 1][j]);
            }
        }
        int num = ans[n][n];
        System.out.println(ans[n][n]);
        char[] end = new char[num];
        int i = n, j = n, flag = num;
        while (flag > 0){
            if (ans[i][j] == flag && b[i - 1] == a[j - 1]){
                end[flag - 1] = b[i - 1];
                i--; j--; flag--;
            }
            else if (ans[i - 1][j] >= ans[i][j - 1]){
                i--;
            }
            else {
                j--;
            }
        }
        return new String(end);
    }
    public static void main(String[] args){

        System.out.println(longestPalindrome("abcbabbba"));
    }
}

发表于 2021-01-10 15:54:10 回复(0)

牛客676809442号

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string longestPalindrome(string s) {
        // write code here
        int n=s.size();
        int len=0;
        int pos;
        vector<vector<bool> > p(n,vector<bool>(n,false));
        for(int i=0;i<n;i++)
        {
            for(int j=i;j>=0;j--)
            {
                if((s[i]==s[j])&&(i-j<2||p[i-1][j+1]))
                {
                    p[i][j]=true;
                    if(i-j+1>=len)
                    {
                        len=i-j+1;
                        pos=j;
                    }
                }
            }
        }
        
        string res=s.substr(pos,len);
        
        return res;
    }
};

发表于 2020-09-07 22:05:45 回复(0)

cqu后起之秀

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    bool Is_Prime(string str){//判断字符串str是否回文
        for(int i=0;i<str.length()/2;i++){
            if(str[i]!=str[str.length()-1-i]){
                return false;
            }
        }
        return true;
    }
    string longestPalindrome(string s) {
        // write code here
        string ans=s.substr(0,1),str;
        for(int i=0;i<s.length();i++){//从字符串首字母遍历
            str=s[i];
            for(int j=i+1;j<s.length();j++){//依次往后加
                str=str+s[j];
                if(Is_Prime(str)&&str.length()>ans.length()){//储存最长的回文
                    ans=str;
                }  
            }
        }
        return ans;
    }
};

发表于 2020-08-29 16:41:09 回复(0)

Python

黄沙遮天

本题主要采用的方法是长短指针，有两个临界点需要考虑，一是第一次出现回文子串，然后r继续增长，二是直到不符合回文子串时，就让l加1.从这两种状态中找出最长的回文子串。另外需要注意的就是在循环结束后，最后的字符串还没处理，可能不是回文字符串，也可能不是。

class Solution:
    def longestPalindrome(self , s ):
        # write code here
        l,r=0,0
        maxstr=''
        flag=0
        while(r!=len(s)):
            temstr=''
            temstr=s[l:r]
            if s[l:r]!=temstr[::-1] and flag==0:
                r+=1
            elif s[l:r]==temstr[::-1] and len(s[l:r])>=2 and flag==0:
                if len(maxstr)<len(s[l:r]):
                    maxstr=s[l:r]
                flag=1
                r+=1
            elif s[l:r]==temstr[::-1] and flag==1:
                if len(maxstr)<len(s[l:r]):
                    maxstr=s[l:r]
                r+=1
            elif s[l:r]!=temstr[::-1] and flag==1:
                l+=1
                if len(maxstr)<len(s[l:r]):
                    maxstr=s[l:r]
            else:
                r+=1
        temstr=s[l:r]
        if s[l:r]==temstr[::-1]:
            if len(maxstr) < len(s[l:r]):
                maxstr = s[l:r]
        elif s[l:r]!=temstr[::-1]:
            while(l<r and s[l:r]!=temstr[::-1]):
                l+=1
                temstr=s[l:r]
            if  s[l:r]==temstr[::-1]:
                if len(maxstr) < len(s[l:r]):
                    maxstr = s[l:r]
        return maxstr

发表于 2020-08-25 15:23:29 回复(1)

Python

Liiy

#python实现
class Solution:
    def longestPalindrome(self , s )-> str:
        # write code here
        res = ''
        for i in range(len(s)):
            start =  max(0,i-len(res)-1)
            temp = s[start:i+1]
            if temp == temp[::-1]:
                res = temp
            else:
                temp = temp[1:]
                if temp == temp[::-1]:
                    res = temp
        return res

发表于 2020-08-10 00:05:05 回复(0)

最长的回文子串

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题