最长回文串 python

leedcode代码Longest Palindromic Substring 最长回文串 python实现

• 题目分析
• Brute-force解法
• Dynamic Programming解法

题目分析

例如aba , abba 是回文的字符串。

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Brute-force解法

这是一种复杂度O(n^2) 的算法。核心的解法为遍历所有的可能性，然后去比较分析是不是回文串，再得到最大的序列，其实这种算法也是不考虑时间和空间复杂度情况下的答案。理解这种算法能够帮助后面的dynamic programming 的解答。

// An highlighted block
class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        length : integer,represnt the length of the string 
        palindromic : Boolean, indicate the palindrome 
        output: string, palindrome string
        max_length: integer, palindrome string length
        
        """
        #length < = 1000
        length = len(s)
        max_length = 0
        # find the start position
        if s =='':
            return s
        if length ==1:
            return s
        else:
            for i in range(length):
                # j represent the end position
                for j in range(i+1,length):
                    palindromic = True
                    left = i
                    right = j
                    if right-left > max_length:
                        while left < right:
                            if s[left] != s[right]:
                                palindromic = False
                                break
                            else:
                                left +=1
                                right -=1
                        if palindromic == True and length >0 :
                            max_length = j-i       
                            output = s[i:j+1]
            if max_length ==0:
                return s[0]
            else:
                return output
           

Dynamic Programming解法

经常在做题的时候碰到这个概念，昨天花了一天的时间理解一下。总体的意思是，节约时间成本，如果有些数据已经计算过了，就没必要让计算机再算一遍。特别像高中的数列和线性规划问题，只是现在让计算机来实现。

// An highlighted block
class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        length : integer,represnt the length of the string  
        output: string, palindrome string
        max_length: integer, palindrome string length
        dy_pro: 2 dimension matrix
        
        """
        # definition
        print(s)
        length = len(s)
        dy_pro = [[0 for i in range(length) ] for i in range(length)]
        max_length = 0
        output =''
        
        # special situation
        if s == '':
            return s
        if length == 1:
            return s
        for i in range (length):
            for j in range(length):
                dy_pro[i][j] = True
        
        #main idea
        for j in range (0,length):
            for i in range(0,j):
                
                dy_pro[i][j] =  (s[i]==s[j]) and ((j-i<=2) or (dy_pro[i+1][j-1]))
                
                if dy_pro[i][j]:
                    if max_length < j-i+1:
                        max_length = j-i+1
                        output = s[i:j+1]  
        if output == '':
            return s[0]
        else:
            return output