牛客-NC17-最长回文子串

方法一：中心扩散法

思路：这里借鉴了weiwei大佬的题解，自己在这写一遍加深印象。
首先， 中心扩散法的基本思想是：遍历每一个下标，以这个下标为中心，利用 回文串中心对称的特点，往两边扩散，看最多能扩散多远。
枚举中心位置时间复杂度为O(N) ，从中心位置扩散得到回文子串的时间复杂度为O(N)，因此，总的时间复杂度为O(N²)。
值得注意的是，回文串在长度为奇数和偶数的时候，中心位置是不一样的，具体来说：

1. 奇数回文串的中心是一个具体的字符，例如：回文串"aba"的中心是字符"b"。
2. 偶数回文串的中心是位于中间的两个字符的空隙，例如：回文串"abba"的中心是两个"b",也可以看成两个"b"中间的空隙。
   贴个图方便理解：
   

import java.util.*;

public class Solution {
   
    static int ret = 0;
    public int getLongestPalindrome(String A, int n) {
   
        // write code here
        // 特判
        if (A == null || n == 0) return ret;
        for (int i = 0; i < n - 1; i++) {
   
            helper(A, i, i); // 以i为中心，向两边扩散
            helper(A, i, i + 1); // 以i和i+1为中心，向两边扩散
        }
        return ret;
    }
    public static void helper(String s, int left, int right) {
   
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
   
            left -= 1;
            right += 1;
        }
        ret = Math.max(ret, right - left - 1);
    }
}

时间复杂度： O(N²)，枚举中心位置时间复杂度为O(N) ，从中心位置扩散得到回文子串的时间复杂度为O(N)，因此，总的时间复杂度为O(N²)。
空间复杂度： O(1)，未使用额外的空间。
总结：这道题没能从回文的本质出发，想到了从一个字符向左右扩散，但自己却没把它变成code，还是要多写才能熟能生巧啊！