最長回文串 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