LeetCode 5. Longest Palindromic Substring Python3

Description

點選檢視題目

Given a string

s

, find the longest palindromic substring in

s

. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”

Output: “bb”

問題分析

這道題是一道

中等題

，題目的意思是給定一個字元串，找出此字元串的最長回文子串，學習過程式設計的人應該對回文字元串比較了解吧！對于這道題，我最先想到的就是暴力搜尋解法，枚舉出此字元串的所有子串，然後判斷是不是回文字元串，我大緻算了下複雜度，是O(n3),我感覺應該會逾時，果然逾時了。。。。

我在浏覽評論區的時候，發現了一個大佬寫的暴力搜尋代碼，非常簡潔，而且還通過了，不由得感慨自己的代碼寫的太菜了，自己還需要多加努力。

其實這道題要考察的是動态規劃，之前沒有認真學過動态規劃，覺得自己現階段解釋也解釋不太清楚，但是看别人的代碼也能了解咋回事，是以就不在這裡解釋了，通過代碼了解就好。

代碼實作

逾時的暴力搜尋代碼

class Solution:
    def longestPalindrome(self, s: str) -> str:
        for i in range(len(s) - 1, -1, -1):
            j = 0
            while j + i < len(s):
                temp = s[j:j + i + 1]
                j += 1
                if self.judge(temp):
                    return temp
        return ""
    def judge(self, s: str) -> bool:
        for i in range(len(s) // 2):
            if s[i] != s[len(s) - i - 1]:
                return False
        return True
           

逾時的案例："aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

通過的暴力搜尋代碼：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        for i in range(len(s), 0, -1):
            for j in range(len(s) - i + 1):
                if s[j:j + i] == s[j:j + i][::-1]:
                    return s[j:j+i]
           

動态規劃實作

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        length = len(s)
        dp = [[False] * length for _ in range(length)]
        left = 0
        right = 0
        for i in range(length - 2, -1, -1):
            dp[i][i] = True
            for j in range(i+1, length):
                dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i + 1][j - 1])
                # j - i < 3 時，其實j - i要麼等于1（aa）要麼等于2(aba)，無論哪種情況都滿足
                if dp[i][j] and right - left < j - i:
                    right = j
                    left = i
        return s[left:right + 1]
           

運作結果對比

從圖中可以看出，自己寫的代碼遠不如Python自帶的高效，是以要多看别人寫的優秀代碼，以提高自己的程式設計能力。

ok!大功告成了，如果你有其他的方法或者問題，歡迎在評論區交流。