最长回文子串三种解法

解法1，动态规划之带备忘（table）的自顶向下法，建立一个二维表table来记录A[i:j]是否是回文子串,若 table[i][j] == 1则A[1:j+1]为回文串。

# -*- coding:utf-8 -*-

class Palindrome:
    def getLongestPalindrome(self, A, n):
        # write code here
        if n <= 1:
            return n
        table = [[-1 for _ in range(n)] for __ in range(n)]
        for i in range(n):
            table[i][i] = 1
        res = [1]
        def f(left, right):
            if table[left][right] != -1:
                return table[left][right] == 1
            if left > right:
                return False
            if A[left] == A[right]:
                if 0 <= right - left <= 1 or f(left+1, right-1):
                    table[left][right] = 1
                    res[0] = max(res[0], right - left + 1)
                else:
                    table[left][right] = 0
                    f(left, right-1)
                    f(left+1, right)
            else:
                table[left][right] = 0
                f(left, right-1)
                f(left+1, right)
            return table[left][right] == 1
        f(0, n-1)
        return res[0]

解法2，自底向上法，以更短的回文子串为中心，向两边扩散，不需要建表，而且因为有剪枝处理，效率高。

# -*- coding:utf-8 -*-

class Palindrome:
    def getLongestPalindrome(self, A, n):
        # write code here
        def func(A, left, right):
            while left >=0 and right < n and A[left]==A[right]:
                left -= 1
                right += 1

            return right-left-1

        res = 0
        for i in range(n-1):
            res = max(res, func(A, i, i), func(A, i, i+1))
        return res

解法3，暴力法

# -*- coding:utf-8 -*-

class Palindrome:
    def getLongestPalindrome(self, A, n):
        # write code here
        if n <= 1:
            return n
        res = 1
        for i in range(0,n):
            if n - i <= res:
                return res
            for j in range(n - 1, i, -1):
                if A[j] == A[i]:
                    res = max(res, self.f(A[i:j+1]))


    def f(self, string):
        if string == string[::-1]:
            return len(string)

解法2为最优。