首页 > 试题广场 > 最长回文子串
[编程题]最长回文子串
  • 热度指数:32994 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。

给定字符串A以及它的长度n,请返回最长回文子串的长度。

示例1

输入

"abc1234321ab",12

输出

7
*t头像 *t
动态规划:
public int getLongestPalindrome(String A, int n) {
    		
    		// 第 i 个字符到第 j 个字符是否是回文串
    		boolean[][] dp = new boolean[n][n];
    		int max = 0;
    		// 字符串首尾字母长度差 (d = j-i)
    		for (int d = 0; d < n; d++) {
    			// 字符串起始位置 i
			for (int i = 0; i < n-d; i++) {
				// 字符串结束位置 j
				int j = i+d;
				// 如果字符串 i 到 j 的首尾相等,再根据字符串 i-1 到 j-1 来确定,即得到递推公式
				if(A.charAt(i) == A.charAt(j)) {
					if(d == 0 || d == 1) {
						dp[i][j] = true;
					} else {
						dp[i][j] = dp[i+1][j-1];
					}
					if(dp[i][j]) {
						// 更新最大长度
						max = Math.max(max, d+1);
					}
				}
			}
		}
    		return max;
    }
发表于 2017-08-23 15:43:46 回复(9)
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here int[][] dp = new int[n][n]; int max = 1; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } char[] a = A.toCharArray(); for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; if (len == 2 && a[i] == a[j]) { dp[i][j] = len; max = 2; continue; } if (a[i] == a[j] && dp[i + 1][j - 1] != 0) { dp[i][j] = len; max = len; } } } return max; } }
动态规划
1.dp[i][j]表示,若i到j已经是回文串了,那么dp[i][j]是回文串的长度,否则为0;
2.初始时dp[i][i]=1,i=0,2,3...n-1;
3.递归公式,len>2时,当dp[i+1][j-1]!=0,且a[i]==a[j]时,dp[i][j] = j-i+1+dp[i+1][j-1],  否则dp[i][j]=0,i<j。这是一个从已知回文串往两边展开的过程。当len=2时,特殊处理一下,因为当len=2时,dp[i+1][j-1]会访问到dp矩阵的左下方,我们没对那个位置做初始化处理,因此不能直接用递推公式
发表于 2016-09-13 10:36:41 回复(4)

从头到尾扫描字符串,每增加一个新的字符,判断以这个字符结尾,且长度为maxLen+1或者maxLen+2的子串是否为回文,如果是,更新。

class Solution:
    def getLongestPalindrome(self, A, n):
        maxLen=1
        if A==A[::-1]:return n
        for i in range(n):
            if i-maxLen>=1 and A[i-maxLen-1:i+1]==A[i-maxLen-1:i+1][::-1]:
                maxLen+=2
                continue
            if i-maxLen>=0 and A[i-maxLen:i+1]==A[i-maxLen:i+1][::-1]:
                maxLen+=1
        return maxLen
编辑于 2019-03-05 13:18:58 回复(1)
import java.util.*;

public class Solution {
    //判断回文的函数
    public boolean isHuiWen(String A, int n){
        int k = n / 2;
        for (int i = 0; i < k; ++i)
        {
            if (A.charAt(i) != A.charAt(n-1-i))
                return false;
        }
        return true;
    }
    public int getLongestPalindrome(String A, int n) {
        int maxlen=0;
        for(int i=0 ;i< n ;i++){
            for(int j=i+1 ;j<=n ;j++){
                //两层循环遍历出所有的子串,并且逐一判断是否是回文
                if(isHuiWen(A.substring(i, j),j-i)){
                    if(j-i>maxlen)
                        maxlen=j-i;
                }
            }
        }
        return maxlen;
    }
}

编辑于 2016-04-04 23:09:12 回复(8)
时间复杂度有点大,但是挺好懂的。。
class Solution {
public:
    bool pan(string a,int start,int end){
        //判断是否回文
        bool flag=true;
        while(start<=end){
            if(a[start]!=a[end]){
                flag=false;
                break;
            }
            start++;
            end--;
        }
        return flag;
    }
    int getLongestPalindrome(string A, int n) {
        int max=-1;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(A[i]==A[j]&&pan(A,i,j)&&j-i+1>max){
                    max=j-i+1;
                }
            }
        }
        return max;
    }
};


发表于 2018-02-16 15:49:40 回复(0)
//直接暴力,适用于求长度以及具体回文串
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int start,maxlength=0;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                int tmp1,tmp2;
                for(tmp1=i,tmp2=j;tmp1<tmp2;tmp1++,tmp2--)
                {
                    if(A[tmp1]!=A[tmp2])
                        break;
                }
                if(tmp1>=tmp2&&j-i>=maxlength)
                {
                    maxlength=j-i+1;
                    start=i;
                }
            }
        return maxlength;
    }
};


发表于 2018-02-12 09:33:18 回复(1)
哪位大神帮我看看为什么只通过了50%,
"acbdcbbbdbdaaccbcacdacdccababcddabddaaaaaaabdbabcdddaacabacbacbbdabdacddbbadaacbbdcbccacacdabcabacacbbbdcccacdcdcdcbcbabdcdacdddbbabcaccddddddabdacaabccdcabcbcbabacaaaccaccaddabbdadcdacdcdbaadbcabdcdcaaacbcadccbbddbaddcaddcaadcbbcbbdcbdadcddabdddcdbddbbdabaaddcaadd",265
上面这个用例应该输出7,我的输出为8

import java.util.*;
import java.lang.*;

public class Solution {
    //求a和b的最长公共子字符串长度
	public int lcs(String a, String b) {
		int max_len = 0;
		int[][]dp = new int[a.length() + 1][b.length() + 1];
		for (int i = 1; i <= a.length(); i++) {
			for (int j = 1; j <= b.length(); j++) {
				if (a.charAt(i - 1) == b.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
					if (dp[i][j] > max_len)
						max_len = dp[i][j];
				}
			}
		}
		return max_len;
	}
	public int getLongestPalindrome(String A, int n) {
		// write code here
		String B = new StringBuilder(A).reverse().toString();
		return lcs(A, B);
	}
}


编辑于 2017-05-12 16:09:27 回复(8)

寻找字符串中最长的回文串
改进版动态规划,时间复杂度O(n*n),空间复杂度O(n)
从字符串后面开始探索
whetherSolution[j]为1表示A[i,j+1]为回文串
循环过程中,在whetherSolution里面比当前j小的whetherSolution的标记都为上一个i的
(除了i,因为A[i,i+1]单个字符为回文串)
如果得到一个回文串,和过程中保存的最长回文串比较长度。
这个等号是为了取到长度相等时排在前面的回文串。如果去掉是取到排在后面的

def getLongestPalindrome(self, A, n):
    if n <= 1:
        return n
    whetherSolution = [0 for i in range(n)]
    theSolutionMax = 1
    whetherSolution[-1] = 1
    for i in range(n - 2, -1, -1):
        whetherSolution[i] = 1
        for j in range(n - 1, i, -1):
            if whetherSolution[j - 1] and A[i] == A[j]:
                whetherSolution[j] = 1
                if theSolutionMax < j - i + 1:
                    theSolutionMax = j - i + 1
            else:
                whetherSolution[j] = 0
    return theSolutionMax
编辑于 2018-09-23 11:57:37 回复(1)
没用dp和二分hash,直接暴力了,复杂度应该是n方,注意有aba和baab这两种情况,所以i只能每次增加0.5
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
     int currentMax = 1;
    int clength = 1;
    for(double i=0;i<A.size();)
    {
        double index =1;

        if(int(i*10)%10==5)
        {
            index=0.5;
            while(1)
            {
                int left = i-index;
                int right = i+index;
                //if(index==0.5) index =1;
                if(left<0||right>=A.size()||(A[left]!=A[right]))
                {
                
                    break;
                }
                
                if(currentMax<=index)
                {
                    currentMax = index+0.5;
                    clength = currentMax*2;
                }
                index++;
            }
            
        }else
        {
            while(1)
            {
                int left = i-index;
                int right = i+index;
                if(left<0||right>=A.size()||(A[left]!=A[right]))
                {
                
                    break;
                }
                
                if(currentMax<=index)
                {
                    currentMax = index;
                    clength = 2*currentMax+1;
                }
                index++;
            }
        }
        
        i+=0.5;
    }
    return clength;
    }
};

发表于 2018-02-24 21:22:30 回复(0)
public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int[][] dp = new int[n][n];
        int max = 1;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        char[] a = A.toCharArray();
        for(int i=n-2;i>=0;i--){
            for(int j=i;j<n;j++){
                if(j>0&&dp[i+1][j-1]!=0&&a[i]==a[j]||j>0&&i==j-1&&a[i]==a[j])
                    dp[i][j] = 2+dp[i+1][j-1];
                if(dp[i][j]>max)
                    max=dp[i][j];
            }
        }       
        return max;
    }
} 

发表于 2016-12-22 12:30:39 回复(1)
# -*- coding:utf-8 -*-

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        A='#'+'#'.join(A)+'#'
        n=len(A)
        RL=[0]*n
        MaxRight=0
        pos=0
        MaxLen=0
        for i in range(n):
            if i<MaxRight:
                RL[i]=min(RL[2*pos-i], MaxRight-i)
            else:
                RL[i]=1
            while i-RL[i]>=0 and i+RL[i]<n and A[i-RL[i]]==A[i+RL[i]]:
                RL[i]+=1
            if RL[i]+i-1>MaxRight:
                MaxRight=RL[i]+i-1
                pos=i
            MaxLen=max(MaxLen, RL[i])
        return MaxLen-1
# -*- coding:utf-8 -*-

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        A='#'+'#'.join(A)+'#'
        n=len(A)
        RL=[0]*n
        MaxRight=0
        pos=0
        MaxLen=0
        for i in range(n):
            if i<MaxRight:
                RL[i]=min(RL[2*pos-i], MaxRight-i)
            else:
                RL[i]=1
            while i-RL[i]>=0 and i+RL[i]<n and A[i-RL[i]]==A[i+RL[i]]:
                RL[i]+=1
            if RL[i]+i-1>MaxRight:
                MaxRight=RL[i]+i-1
                pos=i
            MaxLen=max(MaxLen, RL[i])
        return MaxLen-1
#搬的,参考了网上的manacher算法的文章

发表于 2016-05-14 09:06:47 回复(0)
中心扩展法
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        int res = 0;
        for (int i = 0;i < A.length();i++) {
            res = Math.max(spread(A, i, i), res);
        }
        
        for (int j = 0;j < A.length()-1;j++) {
            if (A.charAt(j) == A.charAt(j+1)) {
                res = Math.max(spread(A, j, j+1), res);
            }
        }
        
        return res;
    }
    
    public int spread(String A, int start, int end) {
        while (start >= 0 && end < A.length() && A.charAt(start) == A.charAt(end)) {
            start--;
            end++;
        }
        return end-start-1;
    }
}


发表于 2021-01-04 22:26:22 回复(0)
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int maxCount = 0;
        for (int i = 1; i < A.length() ; i++){
            int left = i -1;
            int right = i +1;
            int count = 1;
            maxCount = getMaxCount(A, maxCount, left, right, count);
            left = i -1;
            right = i;
            count = 0;
            maxCount = getMaxCount(A, maxCount, left, right, count);
        }
        // write code here
        return maxCount;
    }

    private int getMaxCount(String A, int maxCount, int left, int right, int count) {
        while (left>= 0 && right <= A.length()-1 && A.charAt(left) == A.charAt(right)){
            left--;
            right++;
            count+=2;
        }
        maxCount = Math.max(count,maxCount);
        return maxCount;
    }
}


发表于 2020-11-08 21:53:32 回复(0)
class Solution {
public:
    int getLongestPalindrome(string s, int n) {
         int res=0;int l,r;
        for(int i=0;i<n;i++)
        {
             l=i-1; r=i+1;
            while(l>=0&&r<=n-1&&s[l]==s[r])
            {
                res=max(res,r-l+1);
                l--;r++;
            }
            
            l=i;r=i+1;
            while(l>=0&&r<=n-1&&s[l]==s[r])
            {
                res=max(res,r-l+1);
                l--;r++;
            }
          
        }
        return res;
        
    }
};//借鉴某位大神的写法写了一遍
发表于 2020-09-04 17:00:20 回复(0)
暂时先写了两种思路:
思路一:直接暴力,遍历每个i,j,判断i到j是否是回文,如果是,记录最长的。
class Solution {
public:
    bool isSolution(string A, int l, int r){
        while(l < r){
            if(A[l++] != A[r--])
                return false;
        }
        return true;
    }
    int getLongestPalindrome(string A, int n) {
        // write code here
        int res = 0;
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(isSolution(A, i, j) && j-i+1 > res)
                    res = j-i+1;
            }
        }
        return res;
    }
};

思路二:先找到回文的中心,然后向两端扩散。分为两种情况:奇数的回文以及偶数的回文。
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int res = 0;
        for(int i = 0; i < n; i++){
            int tmp1 = 1;
            int tmp2 = 2;
            int l, r;
            l = i-1;
            r = i+1;
            while(l >= 0 && r < n && A[l] == A[r]){
                tmp1 += 2;
                l--;
                r++;
            }
            l = i-1;
            r = i+2;
            while(l >= 0 && r < n && A[l] == A[r]){
                tmp2 += 2;
                l--;
                r++;
            }
            res = max(res, tmp1);
            if(A[i] == A[i+1])
                res = max(res, tmp2);
        }
        return res;
    }
};


发表于 2020-08-30 16:45:19 回复(0)
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        if (n < 2) return n;
        
        int max = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; i-j >= 0 && i+j < n; j++)
            {
                if (A[i-j] == A[i+j]) {
                    int t = j*2 + 1;
                    max = t > max ? t : max;
                } else
                    break;
            }
            
            for (int j = 0; i-j-1 >= 0 && i+j <n; j++) {
                if (A[i-j-1] == A[i+j]) {
                    int t = j*2 + 2;
                    max = t > max ? t : max;
                } else
                    break;
            }
        }
        return max; 
    }
    
   
    
};

发表于 2020-03-29 00:56:00 回复(0)
//详情请点击博客链接(链接在最下方)
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        int count=0; //记录每次字符串的长度
        int max=0; //记录最大字符串的长度
        for(int i=0;i<n;i++){
            for(int j=i+1;j<=n;j++){
              String s=A.substring(i,j);//通过for截取出所有可能出现的字符串
              if(isPalindromic(s)){//进行判断:2步骤
                count=s.length();
                 if(max<count){ //进行判断:3步骤
                   max=count;
                 }
               }
            }
        }
        return max;
    }
   public static boolean isPalindromic(String s) {
        int i = 0;
        int j = s.length() - 1;
        while (i <= j) {
            //取出新得到的字符串挨个字符进行比较
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}
————————————————
版权声明:本文为CSDN博主「峰回路转」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_44840148/article/details/105123450

发表于 2020-03-26 17:30:32 回复(0)
class Solution {
public:
    int getLongestPalindrome(string str, int n) {
        int max=0;
        string newstr;
        for(char c:str){
            newstr+="#";
            newstr+=c;
        }
        newstr+="#";
        for(int i=0;i<2*n+1;i++){
            for(int len=0;;len++){
                if(newstr[i-len]!=newstr[i+len]||i-len<0||i+len>=2*n+1){
                    break;
                }
                if(max<len*2+1){
                    max=len*2+1;
                }
            }
        }
        return max/2;
    }
};
没用动态规划,从中心找回文,避免考虑奇偶就在每个字符中间及首位加了#使回文串必为奇数,返回的长度除以2就行了,时间复杂度大概O(n^2),主要容易理解
编辑于 2020-03-22 20:10:23 回复(0)
//仅作记录,方便日后查阅
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
    vector<vector<bool> >dp(n,vector<bool>(n,false));//dp[i][j]记录A[i]与A[j]是否相同
    for(int i=0; i<n; i++)
        dp[i][i]=true;//自身显然相等
    int ans=1;//最短长度为1
    for(int i=n-1; i>=0; i--)//从倒数第二个字符开始比较
    {
        for(int j=i+1; j<n; j++)//j从i+1开始
        {
            if(A[i]==A[j])
            {
                if(j==i+1)
                    dp[i][j]=true;//相邻的字符相等即为true
                else
                    if(dp[i+1][j-1])//不相邻的字符,查看内侧是否相同
                        dp[i][j]=true;
                if(dp[i][j]&&ans<j-i+1)
                    ans=j-i+1;
            }

        }
    }
    return ans;
    }
};

发表于 2018-11-04 22:09:12 回复(0)
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        String str=A;
        int len=str.length();
        int[][] dp=new int[len][len];
        int ans=1;
        for(int i=0;i<len;i++){
            dp[i][i]=1;
            if(i<len-1){
                if(str.charAt(i)==str.charAt(i+1)){
                    dp[i][i+1]=1;
                    ans=2;
                }
            }
        }
        for(int L=3;L<=len;L++){
            for(int i=0;i+L-1<len;i++){
                int j=i+L-1;
                if(str.charAt(i)==str.charAt(j) && dp[i+1][j-1]==1){
                    dp[i][j]=1;
                    ans=L;
                }
            }
        }
        return ans;
    }
}

发表于 2018-10-12 18:27:17 回复(0)