最长回文子串

方法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;
    }
}

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;
    }

#马拉车中心扩散
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

时间复杂度：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;
    }
    
}

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;
    }
}

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;     
    }
}

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
}

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;
    }
}

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;
        
    }
};//借鉴某位大神的写法写了一遍

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; 
    }
    
   
    
};

//详情请点击博客链接（链接在最下方）
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

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;
    }
};

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;
    }
}

//尺取法
//设定left和right，left从0开始，right从left+ans 开始，ans初始化为1. 对整个字符串进行遍历
//首先是 定住left 然后找 right处和left处字符相同，然后判断 这里是不是一个回文
//如果是，可以直接替换，因为每一次的right的起始位置一定是从left加上最大长度ans之后的位置开始
//终止条件也好扣
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        int left = 0, right = 0;
        int ans = 1;
        for (left = 0; left + ans < n; left++) {
            for (right = left + ans; right < n; right++) {
                if (A[right] == A[left]) {
                    if (is_reverse(left, right, A)) {
                        ans = right - left + 1;
                    }
                }
            }
        }
        return ans;
    }
    bool is_reverse(int left, int right, string A) {
        bool is_ok = true;
        while (left <= right) {
            if (A[left] != A[right]) {
                is_ok = false;
                break;
            }
            left++;
            right--;
        }
        return is_ok;
    }
};

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        char[] ar = A.toCharArray();
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < ar.length; i++){
            for(int j = 0; j < ar.length; j++){
                if(ar[i] == ar[j] && i - j <= 2 && i != j){
                    stack.push(i);
                }
                    
            }
        }
        int max_len = 0;
        while(!stack.empty()){
        int center = stack.pop();
        int tmp1 = 0,tmp2 = 0,len = 0,left_same = 0,right_same = 0;
        int ii = center-1;
        while(ii >= 0 && ar[center] == ar[ii]){
            left_same++;
            ii--;
        }
        ii = center + 1;
        while(ii<ar.length && ar[center] == ar[ii]){
            right_same++;
            ii++;
        }
        if(left_same == right_same && left_same != 0){
            tmp1 = center + 1;
            tmp2 = center - 1;
            len++;
        }
        else if(left_same - right_same == 1){
            tmp1 = center;
            tmp2 = center-1;
        }
        else if(left_same == 0 && center - 2 >= 0 && ar[center] == ar[center - 2]){
            tmp1 = center;
            tmp2 = center - 2;
            len++;
        }
        else continue;
        while(tmp1 < ar.length && tmp2 >= 0 && ar[tmp1] == ar[tmp2]){
            len+=2;
            tmp1++;
            tmp2--;
        }
        if(max_len < len)max_len = len;
        }
        return max_len;
    }
}