题目描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。

示例

输入

"abc1234321ab",12

返回值

7

解题思路

  1. 将大问题拆分成小问题，回文子串每每去掉头部和尾部，都会是一个回文子串，向卷心菜一样剥开还是一个小的卷心菜，所以我们要从回文子串最中心着手。
  2. 我们要做的就是遍历回文子串的“中心”，得到中心之后再向外扩散，直到最外层数值不相等。
  3. 因为回文子串的中心可能有 1 个，如 "aba"，也有可能是 2 个， 如 "abba"，所以我们每次遍历中心时都要计算这两种情况，取这两种情况中子串最长的那个数。

Java代码实现

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        char[] cArr = A.toCharArray();
        int max = 1;
        // 遍历数组，获得回文子串的中心
        for (int i = 0; i < n - 1; ++i) {
            // 假设中心只有一个点，向外扩散获得回文子串的长度
            int a = calc(cArr, i, i);
            // 假设中心有两个点，……
            int b = calc(cArr, i, i + 1);
            // 记录最长回文子串
            int currentMax = a > b ? a : b;
            max = currentMax > max ? currentMax : max;
        }
        return max;
    }

    private int calc(char[] cArr, int low, int high) {
        /* 当中心为 1 个点，回文子串初始长度为 1，若为 2 个点，则初始长度为 0
            因为 1 个点的情况如 "abc"，中心点 b 长度就必定是 1
            2 个点如 "abcd" 或 "abbc"，中心点有可能是 "bc" 或 "bb" ，不能保证一致，所以长度为 0
        */
        int count = 1 ^ (high - low);
        if (low == high) {
            --low;
            ++high;
        }
        while (low >= 0 && high < cArr.length) {
            if (cArr[low] == cArr[high]) {
                --low;
                ++high;
                count += 2;
            } else {
                break;
            }
        }
        return count;
    }
}