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!大功告成了，如果你有其他的方法或者问题，欢迎在评论区交流。