LeetCode刷题笔记5:最长回文子串(Python实现)

系统 295 0

题目描述:

给定一个字符串 s ,找到 s 中最长的回文子串。你可以假设  s 的最大长度为 1000。

示例 1:

            
              输入:
            
             "babad"

            
              输出:
            
             "bab"

            
              注意:
            
             "aba" 也是一个有效答案。

          

示例 2:

            
              输入:
            
             "cbbd"

            
              输出:
            
             "bb"

          

Solution(转自LeetCode官方题解):

LeetCode刷题笔记5:最长回文子串(Python实现)_第1张图片

CODE:

            
              class Solution:
    def longestPalindrome(self,s):
        '''
        
        :param s:str 
        :return: str
        '''
        longest = 0
        len_s = len(s)
        dp = [[0 for i in range(len_s)] for i in range(len_s)]
        for j in range(0,len_s):
            for i in range(0,j+1):
                if j-i <= 1:
                    if s[i] == s[j]:
                        dp[i][j] = 1
                        if longest < j-i+1:
                            longest = j-i+1
                            sublongeststr = s[i:j+1]
                else:
                    if j-i > 1:
                        if s[i] == s[j] and dp[i+1][j-1]:
                            dp[i][j] = 1
                            if longest < j-i+1:
                                longest = j-i+1
                                sublongeststr = s[i:j+1]
        return sublongeststr
            
          

 


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

发表我的评论
最新评论 总共0条评论