题解 | #最长回文子串#

方法1：首先将字符串翻转，然后找到原字符串和翻转字符串的最长公共子串，就是最长回文字符串，我自己测试了一些都是正确的，但是提交后只通过了25/26个测试示例，这个不知道是为什么。

方法2：暴力求解。遍历一遍字符串，然后以A[i]元素为中心向两边遍历，看最长回文字符串的长度，不过需要注意的是回文字符串可能是奇数也可能是偶数，因此需要用两种方式从中心向两边扩散。 代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome1(self , A: str) -> int:
        # write code here
        rev = self.reverse(A)
        # 得到最长公共子串
        longstr = 1
        for i in range(len(A)):
            for j in range(i+1):
                if A[j:i+1] in rev:
                    if i-j+1 > longstr:
                        longstr = i-j+1
                    break
        return longstr


    def reverse(self, A):
        new = ''
        for i in range(len(A)):
            new = A[i]+new
        return new

    def getLongestPalindrome(self , A: str) -> int:
        # 用暴力解法，遍历A，以A[i]为中心的最长回文串长度
        longstr = 1
        for i in range(len(A)):
            # 尝试A[i]作为中心
            j = 0 ; leng1 = -1
            while i-j>=0 and i+j<len(A):
                if A[i-j] == A[i+j]:
                    leng1+=2
                    j+=1
                else:
                    break
            #尝试双个作为中心
            j=0 ; leng2 = 0
            if i<len(A)-1 and A[i]==A[i+1]:
                while i-j>=0 and i+1+j<len(A):
                    if A[i-j] == A[i+1+j]:
                        leng2 += 2
                        j+=1
                    else:
                        break
            if max(leng1,leng2) > longstr:
                longstr = max(leng1,leng2)
        return longstr

A = "baabccc"
print(Solution().getLongestPalindrome(A))