题目描述
 
给定一个字符串s，找到 s中最长的回文子串。你可以假设s的最大长度为 1000。
 
LeetCode原题地址：https://leetcode-cn.com/problems/longest-palindromic-substring/
 
测试用例
 
示例 1
 
 
 
输入: “babad”
 输出: “bab”
 注意: “aba” 也是一个有效答案。
 
 
示例 2
 
 
 
输入: “cbbd”
 输出: “bb”
 
 
解题代码和思路
 
遍历所有子串寻找回文子串
 
class Solution(object):
    def validate_palindrome(self,s,left,right):
        """判断字符串是否为回文字符串
        :param s:
        :param left:
        :param right:
        :return:
        """
        if len(s) < right and left < 0:
            assert("s length must greater than right,left must greater than or equal to zero")
        while left < right:
            #回文字符串左边和右边字符相等
            if s[left] != s[right]:
                return False
            #移动左边和右边的指针
            left += 1
            right -= 1
        return True


    def longestPalindrome(self,s):
        s_len = len(s)
        if s_len < 2:
            return s
        #用来记录回文字符串
        palindrome_s = s[0]
        #记录回文字符串长度
        max_len = 1
        #遍历字符串中的所有子串
        for i in range(s_len-1):
            for j in range(i+1,s_len):
                if j-i+1 > max_len and self.validate_palindrome(s,i,j):
                    palindrome_s = s[i:j+1]
                    max_len = j - i + 1

        return palindrome_s
 
动态规划
 
class Solution(object):
    def longestPalindrome(self,s):
        size = len(s)
        #如果字符串的长度为1就是回文字符串
        if size < 2:
            return s
        #创建一个二维列表用来保存每个字符串是否为回文字符串
        is_p = [[False for _ in range(size)] for _ in range(size)]
        #对角线上都是回文字符串,因为都是单个字符
        for i in range(size):
            is_p[i][i] = True

        #用来记录回文字符串的起始位置
        s_index = 0
        max_len = 1
        #遍历表格,计算字符串是否为回文字符串
        for j in range(1,size):
            for i in range(0,j):
                if s[i] == s[j]:
                    if j - i < 3:
                        is_p[i][j] = True
                    else:
                        is_p[i][j] = is_p[i+1][j-1]
                else:
                    is_p[i][j] = False

                #记录最长的回文字符串
                current_len = j - i + 1
                if is_p[i][j] and current_len > max_len:
                    max_len = current_len
                    s_index = i
        return s[s_index:(s_index+max_len)]
 
中心扩散算法
 
class Solution(object):
    def center_spread(self,s,size,left,right):
        """中心扩散寻找回文字符串
        :param s: 字符串
        :param size: 字符串的长度
        :param left: 开始寻找左边的位置
        :param right: 开始寻找右边的位置
        :return: 回文字符串,回文字符串的长度
        """
        i = left
        j = right
        #保证在寻找的过程中不发生越界,而且左右两个字符要相等
        while i >= 0 and j < size and s[i] == s[j]:
            i -= 1
            j += 1

        return s[i+1:j],j-i-1

    def longestPalindrome(self,s):
        size = len(s)
        if size < 2:
            return s
        s_palindrome = s[0]
        max_len = 0
        for i in range(size):
            #当回文字符串是奇数的时候
            odd_palindrome,odd_len = self.center_spread(s,size,i,i)
            #当回文字符串是偶数的时候
            even_palindrom,even_len = self.center_spread(s,size,i,i+1)
            #获取最长的回文字符串
            cur_palindrome = odd_palindrome if odd_len > even_len else even_palindrom
            #更新最长的回文字符串
            if len(cur_palindrome) > max_len:
                s_palindrome = cur_palindrome
                max_len = len(cur_palindrome)

        return s_palindrome
 
Manacher(拉马车) 算法
 
class Solution(object):
    def longestPalindrome(self,s):
        size = len(s)
        if size < 2:
            return s
        #对原始字符串的每个间隙添加一个字符串#
        expand_s = "#"
        for i in range(size):
            expand_s += s[i]
            expand_s += "#"
        #计算扩展之后的字符长度
        expand_s_size = size * 2 + 1
        #初始化P数组
        p = [0 for _ in range(expand_s_size)]
        #定义中心指针和右边界指针
        center = 0
        max_right = 0
        #记录最长回文字符串的起始位置
        start = 1
        #记录回文字符串的长度
        max_len = 1

        for i in range(expand_s_size):
            #利用回文字符的镜像特点,来减少重复的计算
            if i < max_right:
                mirror = 2 * center - i
                #利用镜像计算回文字符串的长度不能超过右边界
                p[i] = min(max_right-i,p[mirror])

            #定义左右两个指针,利用中心扩散算法寻找边界外的回文字符串
            left = i - (1 + p[i])
            right = i + (1 + p[i])
            while left < right and left >= 0 and right < expand_s_size and expand_s[left] == expand_s[right]:
                p[i] += 1
                left -= 1
                right += 1
            #更新最长的右边界和中心位置,尽量减少计算
            if p[i] > max_right:
                max_right = i + p[i]
                center = i
            #计算最长回文字符串
            if p[i] > max_len:
                max_len = p[i]
                start = (i - max_len) // 2

        return s[start:(start+max_len)]
 
参考：
 
LeetCode详细题解
拉马车算法详解

题目描述
 
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
 
给定字符串A以及它的长度n，请返回最长回文子串的长度。
 
测试样例：
 
"abc1234321ab",12
 
返回：7
 
CODE
 
暴力求解一： 
  
2682ms
5752KB
# -*- coding:utf-8 -*-

class Palindrome:
    def getLongestPalindrome(self, A, n):
        # write code here
        if n <= 1:
            return n
        s = int(n /2)
        max_n = 0
        arr = list(A)
        for i in range(n-1):
            i += 1
            step = min(s, n - i)
            for j in range(step):
                j+=1
                c = arr[i]
                tr = arr[i+1 : i+j+1]
                tl = arr[i+1 : i+j+1]
                tl.reverse()
                c1 = []
                c2 = []
                c1.extend(tl)
                c1.extend(c)
                c1.extend(tr)

                c2.extend(tl)
                c2.extend(c)
                c2.extend(c)
                c2.extend(tr)

                if ("".join(c1) in A):
                    max_n = max(max_n, len(c1))
                elif ("".join(c2) in A):
                    max_n = max(max_n, len(c2))
        return max_n
 
暴力求解二： 
  
211ms
32072KB
 public int getLongestPalindrome(String s) {
        if(s == null){
            return 0;
        }
        if(s.length() <= 1)
            return s.length();
        String res=s.substring(0,1);
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String k=s.substring(i,j);
                String rk=new StringBuffer(k).reverse().toString();
                if(k.equals(rk)&&k.length()>res.length()){
                    res=k;
                }
            }

        }
        return res.length();
    }
 
暴力求解三： 
  
115ms
29352KB
public int getLongestPalindrome(String s) {
        if (s == null)
            return 0;
        if(s.length() <= 1)
            return s.length();
        for(int i = s.length();i > 0; i--) {//子串长度
            for (int j = 0; j <= s.length() - i; j++) {
                String sub = s.substring(j , i + j);//子串位置
                int count = 0;//计数，用来判断是否对称
                for (int k = 0; k < sub.length() / 2; k++) {//左右对称判断
                    if (sub.charAt(k) == sub.charAt(sub.length() - k - 1))
                        count++;
                }
                if (count == sub.length() / 2)
                    return sub.length();
            }
        }
        return 1;

    }
 
动态规划： 
  
38ms
11376KB
    public int getLongestPalindrome(String s) {
        if (s == null) {
            return 0;
        }

        if (s.length() <= 1) {
            return s.length();
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int left = 0;
        int right = 0;
        for (int i = n - 2; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3一定是回文
                if(dp[i][j]&&right-left<j-i){
                    left=i;
                    right=j;
                }
            }
        }
        return right - left + 1;
    }
 
Manacher算法(原文：https://blog.csdn.net/qq_32354501/article/details/80084325) 
  
31ms
9832KB
public int getLongestPalindrome(String s) {
        if (s == null) {
            return 0;
        }

        if (s.length() <= 1) {        
            return s.length();
        }

        List<Character> s_new = new ArrayList<>();
        for(int i = 0;i < s.length();i++){
            s_new.add('#');
            s_new.add(s.charAt(i));
        }
        s_new.add('#');
        List<Integer> Len = new ArrayList<>();
        String sub = "";//最长回文子串
        int sub_midd = 0;//表示在i之前所得到的Len数组中的最大值所在位置
        int sub_side = 0;//表示以sub_midd为中心的最长回文子串的最右端在S_new中的位置
        Len.add(1);
        for(int i = 1;i < s_new.size();i++){
            if(i < sub_side) {//i < sub_side时，在Len[j]和sub_side - i中取最小值，省去了j的判断
                int j = 2 * sub_midd - i;
                if(j >= 2 * sub_midd - sub_side &&  Len.get(j) <= sub_side - i){
                    Len.add(Len.get(j));
                }
                else
                    Len.add(sub_side - i + 1);
            }
            else//i >= sub_side时，从头开始匹配
                Len.add(1);
            while( (i - Len.get(i) >= 0 && i + Len.get(i) < s_new.size()) && (s_new.get(i - Len.get(i)) == s_new.get(i + Len.get(i))))
                Len.set(i,Len.get(i) + 1);//s_new[i]两端开始扩展匹配，直到匹配失败时停止
            if(Len.get(i) >= Len.get(sub_midd)){//匹配的新回文子串长度大于原有的长度
                sub_side = Len.get(i) + i - 1;
                sub_midd = i;
            }
        }
        sub = s.substring((2*sub_midd - sub_side)/2,sub_side /2);//在s中找到最长回文子串的位置
        return sub.length();

    }
 
思想
 
参考文章：https://blog.csdn.net/SeaSky_Steven/article/details/108603928

1 问题描述
 给定一个字符串，求它的最长回文子串的长度。
 
2 解决方案
 2.1 中心扩展法
 此处，首先枚举出回文串的中心位置，然后，再在该位置上分别向左和向右扩展，记录并更新得到的最长回文串的长度。
 
package com.liuzhen.string_1;

import java.util.Scanner;

public class StringLongestPalindrome {
    /*
     * 参数A：给定字符串
     * 函数功能：返回字符串A中最长回文串的长度
     */
    public int getLongestPalindrome(String A){
        char[] arrayA = A.toCharArray();
        int max = 0;
        int tempMax = 0;
        if(A.equals("") || A.equals(null))
            return 0;
        for(int i = 0;i < arrayA.length;i++){  //i为回文串的中心位置
            //当回文串位数为奇数时
            for(int j = 0;(i-j) >= 0 && (i+j) < arrayA.length;j++){
                if(arrayA[i-j] != arrayA[i+j])
                    break;
                tempMax = 2*j + 1;
            }
            if(tempMax > max)
                max = tempMax;
            //当回文串位数为偶数时
            for(int j = 0;(i-j) >= 0 && (i+j+1) < arrayA.length;j++){
                if(arrayA[i-j] != arrayA[i+j+1])
                    break;
                tempMax = 2*j + 2;
            }
            if(tempMax > max)
                max = tempMax;
        }
        return max;
    }
    
    public static void main(String[] args){
        StringLongestPalindrome test = new StringLongestPalindrome();
        Scanner in = new Scanner(System.in);
        System.out.println("请输入一个字符串：");
        String A = in.nextLine();
        int maxA = test.getLongestPalindrome(A);
        System.out.println("输入目标字符串中最长回文串的长度为："+maxA);
    }
}
 
运行结果：
 
请输入一个字符串：
abba
输入目标字符串中最长回文串的长度为：4


请输入一个字符串：
aabbbbba
输入目标字符串中最长回文串的长度为：7


请输入一个字符串：
我爱爱我我我啊
输入目标字符串中最长回文串的长度为：4
 
2.2 Manacher算法
 
package com.liuzhen.practice;

import java.util.Scanner;

public class Main {
    
    public void Manacher(String A) {
        StringBuffer s = new StringBuffer("$#");
        for(int i = 0;i < A.length();i++) {
            s.append(A.charAt(i));
            s.append("#");
        }
        A = s.toString();
        int[] P = new int[A.length()];
        int mx = 0, id = 0;
        for(int i = 1;i < A.length();i++) {
            if(mx > i)
                P[i] = Math.min(P[2 * id - i], mx - i);
            else
                P[i] = 1;
            while(i + P[i] < A.length() && i - P[i] >= 0 && A.charAt(i + P[i]) == A.charAt(i - P[i])) {
                P[i]++;
            }
            if(P[i] + i > mx) {
                mx = i + P[i];
                id = i;
            }
        }
        int result = -1;
        int i = 0, t = 0;
        for(;i < P.length;i++) {
            if(P[i] > result) {
                result = P[i];
                t = i;
            }
        }
        for(int j = t - result + 1;j <= t + result - 1;j++) {
            if(A.charAt(j) != '#')
            System.out.print(A.charAt(j));
        }
        System.out.println("\n最长字符串长度："+(result-1));
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        String A = in.next();
        test.Manacher(A);
    }
}
 
运行结果：
 
abba
abba
最长字符串长度：4
12321
最长字符串长度：5


我爱你爱我
我爱你爱我
最长字符串长度：5


我爱她
我
最长字符串长度：1

1 题目链接
 
最长回文子串长度
 
2 题目描述
 
 
 
描述
 
 
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
 给定字符串A以及它的长度n，请返回最长回文子串的长度。
 
 
 
示例
 
 
输入:"abc1234321ab",12
返回值:7
 
3 代码实现
 
public class Solution {
    public int getLongestPalindrome(String A, int n) {
        boolean[][] dp = new boolean[n][n]; // 记录从i到j是否回文，这道题目，动态规划用于简化判断回文。如果不用动态规划，还需要一个循环判断回文。abcba串中的bcb串的回文判断是多余的。因为在bcb回文的时候已经判断过了
        int max = 0;
        char []charArray = A.toCharArray();
        // 循环i和循环j找到从i到j的所有字符串
        for(int j = 0; j < n; j++){
            for(int i = 0; i <= j; i++){
                // 两边的值如果相等，则根据i+1到j-1的回文状态得出i到j回文
                if(A.charAt(i) == A.charAt(j)){
                    // 二者同时指向一个位置，或者二者本身相邻，则回文
                    if(i == j || j - i == 1){  
                        dp[i][j] = true;
                    }else{
                        // 否则内部回文则回文
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    if(dp[i][j] == true){
                        max = Math.max(max,j - i + 1);
                    }
                }
            }
        }
        return max;
    }
}
 
5 相关例题
 
最长回文子串
 
class Solution {
    public String longestPalindrome(String s) {
        boolean [][]dp = new boolean[s.length()][s.length()];
        String maxStr = "";
        for(int j = 0; j < s.length(); j++){
            for(int i = 0; i <= j; i++){
                if(s.charAt(i) == s.charAt(j)){
                    if(i == j || i + 1 == j){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    // 区别在这，需要把回文串记录下来
                    if(dp[i][j] == true && j - i + 1 > maxStr.length()){
                        maxStr = s.substring(i, j + 1);
                    }
                }
            }
        }
        return maxStr;
    }
}