「笔试刷题」：最长回文子串（中心扩展算法）

一、题目

描述

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

数据范围： 1≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n^2)

进阶:  空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

"ababc"

返回值：

3

说明：

最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：

"abbba"

返回值：

5

示例3

输入：

"b"

返回值：

1

二、思路解析

关于最长回文子串的这道题，我以前写过一篇博客，不过用的是动态规划来解决的，附上链接👇

「优选算法刷题」：最长回文子串http://t.csdnimg.cn/Z6dvA

那本篇博客，我就换了 中心扩展算法 来做这道题，这也是我第一次接触到这个算法~

回文子串问题，重点在于判断奇偶性对于结果的影响。

从字符串的每个字符开始（用一层 for 循环来遍历），以该字符为中心向两边扩展，判断是否构成回文串，记录最长回文串的长度。

那我们先计算回文子串为偶数时的情况，这时候左边界 left 为 i - 1 ，右边界为 i + 1，然后再用 一层 whlie 循环，使 left 和 right 都到达临界点。

然后，同样是一层 while 循环，但这次 左边界 left 为 i，右边界为 i + 1，因为我们判断的是回文子串为奇数时的情况了。

遍历完所有字符后，即可得到最长回文子串的长度，具体实现请看下面代码👇

三、完整代码

import java.util.*;


public class Solution {
    public int getLongestPalindrome (String A) {
        int n = A.length();
        int ret = 0;

        for(int i = 0; i < n; i++){
            int left = i - 1;
            int right = i + 1;
            while(right < n && left >= 0 && A.charAt(left) == A.charAt(right)){
                right++;
                left--;
            }
            ret = Math.max(ret, right - left - 1);

            left = i;
            right = i + 1;
            while(right < n && left >= 0 && A.charAt(left) == A.charAt(right)){
                right++;
                left--;
            }
            ret = Math.max(ret, right - left - 1);            
        }
        return ret;
    }
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！