首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串
  • 热度指数:216885 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

对于长度为n的一个字符串A(仅包含数字,大小写英文字母),请设计一个高效算法,计算其中最长回文子串的长度。


数据范围:
要求:空间复杂度 ,时间复杂度
进阶:  空间复杂度 ,时间复杂度
示例1

输入

"ababc"

输出

3

说明

最长的回文子串为"aba"与"bab",长度都为3
示例2

输入

"abbba"

输出

5
示例3

输入

"b"

输出

1
时间复杂度有点大,但是挺好懂的。。
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 回复(3)
没用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)
int getLongestPalindrome(string A) {
        // write code here
        vector<vector<int> >dp(A.size(), vector<int>(A.size()));
        int ret = 1;
        for(int i = 0; i < A.size(); ++i)
        {
            dp[i][i] = 1;
            if(i < A.size() - 1)
            {
                if(A[i] == A[i+1])
                {
                    dp[i][i+1] = 1;
                    ret = 2;
                }
            }
        }
        
        for(int L = 3; L <= A.size() ;++L)
            for(int i = 0; i + L - 1 < A.size(); ++i)
            {
                int j = i + L - 1;
                if(A[i] == A[j] && dp[i + 1][j - 1])
                {
                    dp[i][j] = 1;
                    ret = L;
                }
            }
        return ret;
    }
都会背了...
发表于 2022-07-28 22:52:42 回复(0)

manacher算法
时间复杂度:O(n) 空间复杂度:O(n)
参考文献:Manacher算法的详细讲解

class Solution:
    def manacher(self, s, n, dp):
        ms = ''
        ms += '$#'
        for i in range(n):
            ms += s[i]
            ms += '#'
        index = 0
        maxpos = 0
        for i in range(len(ms)):
            if i < maxpos:
                dp[i] = min(dp[2*index-i], maxpos-i)
            else:
                dp[i] = 1
            while i - dp[i] > 0 and i + dp[i] < len(ms) and ms[i-dp[i]] == ms[i+dp[i]]:
                dp[i] += 1
            if i + dp[i] > maxpos:
                maxpos = i + dp[i]
                index = i

    def getLongestPalindrome(self , A: str) -> int:
        n = len(A)
        dp = [0 for i in range(n*2 + 2)]
        self.manacher(A, n, dp)
        res = 0
        for i in range(n*2+2):
            res = max(res, dp[i]-1)
        return res
发表于 2022-06-22 16:06:12 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def fun(self, s, left, right):
        while left >=0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    # Manacher算法, 感觉有点想剪枝的策略
    def Manacher(self, s):
        S = '#'.join(list(s))
        S = '@#' + S + '#'
        P = [0 for _ in range(len(S)+10)]
        idx, mx, max_num, max_id= 0,0,0,0

        for i in range(1, len(S)):
            # 如果当前的i在最大回文半径内,则进行选择当前最大半径下标到当前下标的距离  和  对称位置2*idx - 1的最大半径 最小值
            # 然后进行从对应的半径P[i]进行开始向左和右进行搜索
            P[i] = min(P[2 * idx - i], mx - i) if mx > i else 1
            while i - P[i] >=0 and i + P[i] < len(S) and S[i + P[i]] == S[i - P[i]]:
                P[i] += 1
            # 如果当前的最大半径index大于当前的mx,则进行替换
            # 更新最大回文半径中心id
            if i + P[i] > mx:
                mx = i + P[i]
                idx = i
            if P[i] > max_num:
                max_num = P[i]
                max_id = idx
        return max_num - 1            
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        # 最长回文子串 O(n^2)
        # 从左到右进行遍历字符串,然后计算1、中心字符扩散;2、两个字符扩散
#         rel = 1
#         for i in range(len(A) - 1):
#             rel = max(rel, max(self.fun(A, i, i), self.fun(A, i, i+1)))
        return self.Manacher(A)

TIPS:对于O(n^2)的做法:
1、通过将字符串进行反转,然后使用动态规划计算和原始字符串的最长共同子串;
2、通过中心扩散的做法, 遍历一遍字符串,对于每个字符进行向两边扩散计算回文子串的最大长度;

对于时间复杂度O(n)的做法:
Manacher算法:
1、首先将字符串‘123456’,处理成‘@#1#2#3#4#5#6#’的形式;
2、然后设定一个备忘录dp[i],记录节点i的最大回文子串半径大小,设定额外两个变量idx,max_b,分别表示遍历过程中,当前字符前最大回文子串的中心下标以及最大回文子串的右界;
3、从头开始遍历,如果最大有界大于当前所遍历的字符下标,则取min(右界到当前下标的距离,当前下标在当下最大回文子串中心对称字符的最大半径P[2 *idx - cur_index]]),否则直接设定为1,
4、对当前字符可能的最大半径之后,进而从半径大小开始向两端遍历
5、如果更新后的当前字符的最大半径【右界】大于当前的右界,则进行更新右界和最大回文字符中心index
6、更新结果max_num【最终的max_num - 1则是最长回文子串的长度】

发表于 2022-05-08 20:39:47 回复(0)
public int getLongestPalindrome(String A, int n) {
        //一个字符肯定为1
        if(A.length()==1) return 1;
        //两个字符并且相同肯定为2
        if(A.length()==2&&A.charAt(0)==A.charAt(1)) return 2;
        //两个字符并且不相同相同肯定为1
        if(A.length()==2&&A.charAt(0)!=A.charAt(1)) return 1;
        int maxLen = 0;
        for(int i=0; i<A.length(); i++){
            ArrayList<Integer> list = new ArrayList<Integer>();
            char tmp = A.charAt(i);
            //双层遍历,0-A.length() 1-A.length.......
            for(int j=i+1; j<A.length(); j++){
                if(A.charAt(j) == tmp){
                    list.add(j);
                }
            }
            //遍历list
            for(int k=0; k<list.size(); k++){
                //因为substring()含头不含尾所以+1
                Boolean flag = check(A.substring(i, list.get(k)+1));
                //成功就截取长度
                if(flag){
                    maxLen = Math.max(maxLen,list.get(k)-i+1);
                }
            }
        }
        return maxLen;
    }
    public boolean check(String s){
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)!=s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }

发表于 2021-11-27 20:52:18 回复(0)

方法1:中心扩展法

public class Solution {
    // 方法1:遍历,时间复杂度为 O(n^2)
    public int getLongestPalindrome(String A, int n) {
        int maxLen = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // 这里一定要注意奇数长度和偶数长度的回文串都要考虑
            maxLen=Math.max(maxLen,getMaxHui(i-1,i+1,A));
            maxLen=Math.max(maxLen,getMaxHui(i,i+1,A));
        }
        return maxLen;
    }

    // 获取指定 l r 开始的最长的回文串长度
    private int getMaxHui(int l,int r,String A) {
        while (l>=0 && r<=A.length()-1 && A.charAt(l)==A.charAt(r)) {
            l--;
            r++;
        }
        return r-l-1;
    }
}

方法2:动态规划

public class Solution {
   public int getLongestPalindrome(String A) {
       if (A.length()<=1) return A.length();
        int n = A.length();
        int[][] dp = new int[n][n];
        int res = 1;
        int len = A.length();
        // 长度为 1 的串,肯定是回文的
        for (int i = 0; i < n; i++) {
            dp[i][i]=1;
        }
        // 将长度为 2-str.length 的所有串遍历一遍
        for (int step = 2; step <= A.length(); step++) {
            for (int l = 0; l < A.length(); l++) {
                int r=l+step-1;
                if (r>=len) break;
                if (A.charAt(l)==A.charAt(r)) {
                    if (r-l==1) dp[l][r]=2;
                    else dp[l][r]=dp[l+1][r-1]==0?0:dp[l+1][r-1]+2;
                }
                res=Math.max(res,dp[l][r]);
            }
        }
        return res;
    }
}
发表于 2021-11-17 15:44:35 回复(2)
public int getLongestPalindrome(String A, int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        int maxLen = 1;
        for(int i = 0; i<n; i++){
            for(int j = 1; i-j>=0 && i+j<n; j++){
                if(A.charAt(i-j) == A.charAt(i+j)){
                    int len = 2*j+1;
                    maxLen = Math.max(len,maxLen);
                }
                if(A.charAt(i-j) != A.charAt(i+j))break;
            }

            for(int k = 1; i-k+1>=0 && i+k<n; k++){
                if(A.charAt(i-k+1) == A.charAt(i+k) ) {
                    int len = 2*k;
                    maxLen = Math.max(len,maxLen);
                }
                if(A.charAt(i-k+1) != A.charAt(i+k)) break;
            }
        }
   
        return maxLen;
    }

发表于 2021-08-21 14:52:05 回复(0)
#马拉车中心扩散
class Solution:
    def getLongestPalindrome(self, A, n):
        strin = []
        A = list(A)
        A.reverse()
        for i in range(2*n+1):
            if i % 2 == 0:
                strin.append('*')
            else:
                strin.append(A.pop())
        maxr = 0
        for index,item in enumerate(strin):
            step = 1
            try:
                while strin[index-step] == strin[index+step]:
                    step+=1
            except:
                rest = step - 1
                if rest > maxr:
                    maxr = rest
                continue
            rest = step - 1
            if rest > maxr:
                maxr = rest
        return maxr
发表于 2021-07-31 21:34:23 回复(0)
我是直接循环与下一个或者下下一个字符比对,哪位大佬能看出来我哪出错了
用例输入: "dacbcbcabacaabcbcbdaaccacdddabdbcdcdbdabccbdababdaccbbbaccdaaacbbdcdadcacdbcbcacacaddbcbbcadccacdaabddacbcbbcdcadcbbcdddccdccdcbbbaabdadabdbbcbababacbbddbcdbdbbdabaaaaabacadbadbbadabccbbadbcdbcbaadbbddcacdbacadccbccdbacabacaacdbdcbcabbbccdadcbaccccccaaacbbbcbacdadaadcdbacaaadcbdccbcbcdacbababbc",295
预期输出 9
实际输出 8
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int Max = 0,i = 0,j = 0,k = 0,tmp = 0;
        for(i = 0; i < n;i++)
        {
            if(A[i] != A[i + 1] && A[i] != A[i + 2])
            {
                continue;
            }else{
                if(A[i] == A[i + 1])
                {
                    if(A[i] != A[i + 2])
                    {
                        tmp = 2;
                        k = i+2;
                    }else{
                        if(A[i - 1] == A[i + 2])
                        {
                            tmp = 2;
                            k = i+2;
                        }else{
                            tmp = 3;
                            k = i + 3;
                        }
                    }
                }else if(A[i] == A[i + 2])
                {
                    tmp = 3;
                    k = i + 3;
                }
                for(j = i-1;j >= 0 && k <= n;j--,k++)
                {
                    if(A[j] == A[k])
                    {
                        tmp += 2;
                    }else{
                        break;
                    }
                }
                if(Max < tmp)
                    Max = tmp;
            }
        }
        return Max;
    }
};
发表于 2021-06-24 02:15:03 回复(0)
时间复杂度:o(n)

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        char[] chars = A.toCharArray();
        int max = 1;
        int left,right;
        for(int i = 0 ; i < n;i++){
            int res1 = process(chars,i-1,i+1,n,1);
            int res2 = process(chars,i,i+1,n,0);
            int count = Math.max(res1,res2);
            max = Math.max(count,max);
        }
        return max;
    }
    
    public int process(char[] chars , int left,int right,int n,int count){

        while(left>=0 && right<n){
                  if(chars[left] != chars[right]){
                    break;
                }
                count+=2;
                left--;
                right++;
            }
        return count;
    }
    
}

编辑于 2021-05-18 15:03:47 回复(0)

//动态规划
int getLongestPalindrome(string A, int n) {
        // write code here
        int res=1;
        vector<vector<bool>> dp(n,vector<bool>(n,false)); //dp[i][j]:从i到j的字符子串是不是回文串
        for(int i=0; i<n; i++)
        {
            dp[i][i]=true;
        }
        for(int j=1; j<n; j++)
        {
            for(int i=0; i<j; i++)
            {
                if(A[i]!=A[j])
                    dp[i][j]=false;
                else
                {
                    if(j-i+1<=3)  //如果长度小于等于3,直接就是回文串
                        dp[i][j]=true;
                    else //长度大于等于4
                        dp[i][j]=dp[i+1][j-1];
                }
                
                if(dp[i][j] && j-i+1>res)  //更新最大长度
                    res = j-i+1;
            }
        }
        return res;

//中心扩散
    int sublen(string& A, int l, int r)
    {
        while(l>=0 && r<A.size() && A[l]==A[r])
        {
            l--;
            r++;
        }
        return r-l-1;
    }
    
    int getLongestPalindrome(string A, int n) {
        int res=1;
        for(int i=0; i<n; i++)
        {
            int r1 = sublen(A, i, i);
            int r2 = sublen(A, i, i+1);
            
            res = res>r1?res:r1;
            res = res>r2?res:r2;
        }
        return res;
    }



编辑于 2021-05-14 18:02:00 回复(0)
暴力解法,数据量小就可以,要是数据量大就会超时了
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if(n<2){
            return n;
        }
        int maxLength=1;
        int begin=0;
        char[] chararray=A.toCharArray();
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(j-i+1>maxLength && validPalindrome(chararray,i,j)){
                    maxLength=j-i+1;
                    begin=i;
                }
            }
        }
        return maxLength;
    }
    public boolean validPalindrome(char[] chararray,int left,int right){
        while(left<right){
            if(chararray[left]!=chararray[right]){
                return false;
        }
            left++;
            right--;
        }
        return true;
    }
}


发表于 2021-04-16 20:18:39 回复(0)
import java.util.*;
//喜极而泣啊!写代码五分钟,调bug2小时
//说下思路:
public class Solution{
public int getLongestPalindrome(String A, int n) {
            char [] strArr = A.toCharArray();
            int length=0;
    		// l为左,r为右,当l到r范围的字符串为回文,(两端相等,并依次递归,直到所有相等,则为回文)
    		for (int l=0; l < n; l++) {
			for (int r = l; r < n; r++) {
                //设置一个flag,当回文时为1,不回文为-1
                int flag=0,r1=r,l1=l;
                while(l1<=r1)
                {
                    if(strArr[l1]==strArr[r1])
                        flag=1;
                    else
                    {flag=-1;break;}
                    l1++;
                    r1--;
                }
                if(flag==1)length=Math.max(length,r-l+1);
                }
		}
    		return length;
    }
}

发表于 2021-04-02 22:00:11 回复(0)
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        int [][] dp = new int [n+1][n+1];
        int res = 1;
        for(int i = 0;i < n;++i)
            dp[i][i] = 1;
        for(int i = 0,j = i+1;i < n && j < n;++i,++j){
            if(A.charAt(i) == A.charAt(j)){
                dp[i][j] = 2;
                res = 2;
            }    
            else
                dp[i][j] = 0;
        }
        int dis = 2;
        while(dis < n){
            for(int i = 0,j = i+dis;j < n;++i,++j){
                 if(A.charAt(i) == A.charAt(j) && dp[i+1][j-1] != 0){
                    dp[i][j] = 2+dp[i+1][j-1];
                    res = Math.max(dp[i][j],res);
                 }else
                     dp[i][j] = 0;    
            }
            ++dis;
        }
        return res;     
    }
}

发表于 2021-03-29 19:27:56 回复(0)
解题思路:动态规划,len从短到长遍历,dp[i][j]表示从位置i到位置j的最大回文子串长度
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]=2;
                    if(max<2) max=2;
                }
                if(a[i]==a[j]&&dp[i+1][j-1]!=0){
                    dp[i][j]=len;
                    if(max<len) max=len;
                }
            }
        }
        return max;
    }
}
发表于 2021-03-15 09:35:47 回复(0)
export function getLongestPalindrome(A: string, n: number): number {
    // write code here
   if(!n) return 0
    let res = 1
    const dp = []
    for(let i = n -1;i>=0;i--){
        dp[i] = []
        for(let j = i;j<n;j++){
            if(j - i == 0) dp[i][j] = true
            else if(A[i] == A[j]&&j-i == 1) dp[i][j] = true
            else if(A[i] == A[j] && dp[i+1][j-1]) dp[i][j] = true
            if( dp[i][j]&& j - i + 1 >res)  res = j - i + 1
        }
    }
        return res
}

发表于 2021-01-07 19:25:17 回复(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)
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)