NC17 最长回文子串

题目描述

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

输入：
"abc1234321ab",12

返回值：
7

解题思路

先视字符串的每一个字符为回文字符串的中心点。
使用双指针（head = tail = 中心点）从这个中心点向外扩散，如果头尾指针指向的值相同时，说明扩散成功，回文的长度+2。
需要注意回文子串有两种情况：aba型和abba型。如果是abba型，需要提前将tail延后到最后一个重复的字符。

解题代码

class Solution:
    def getLongestPalindrome(self, A, n):
        if n == 0:
            return 0
        max_length = 0
        for i in range(0, n - 1):
            length = -1
            head, tail, j = i, i, i+1
            while j < n - 1:
                # 这里是为了防止出现连续的相同字符干扰判断
                if A[i] == A[j]:
                    tail += 1 # head还是那个head，但是tail移到相同字符的最后一个
                    length += 1
                else:
                    break
                j += 1
            # 找到回文字符串的中心点（单字符的中心点是它自己）
            while head >= 0 and tail <= n - 1:
                if A[head] == A[tail]:
                    length += 2
                    head -= 1
                    tail += 1
                else:
                    break
            max_length = max(length, max_length)
        return max_length

执行结果

55ms 7020kB