转载

最长回文子串

最长回文子串

基本的思想:动态规划,是一种解决方法

class Solution(object):
    def longestPalindrome(self, s):
        """ :type s: str :rtype: str """
        length = len(s)

        arr = [[False for i in range(length)] for j in range(length)]

        for i in range(length):
            arr[i][i] = True

        first = 0
        end = 0  
        for i in range(2, length+1):
            if i == 2:
                for j in range(length-i + 1):
                    if s[j] == s[j + i -1]:
                        #print j, j +i -1
                        arr[j][j+i-1] = True
                        if end - first + 1 < i:
                            first = j
                            end = j + i - 1
            else:
                #print length - i + 1
                for j in range(length-i + 1):
                    #print s[j], s[j+i-1], j+1, j+i-2
                    if s[j] == s[j+i-1] and arr[j+1][j+i-2] == True:
                        #print j, j +i -1
                        arr[j][j+i-1] = True
                        if end - first + 1 < i:
                            first = j
                            end = j + i - 1
        return s[first : end + 1]
正文到此结束
本文目录