【Python】【LeetCode】【5.最长回文字符串】

Love The Way You Lie 2022-01-29 23:59 188阅读 0赞

### 文章目录 ###

*   *   *  0.回文字符串
         *  1.原文题目
         *  2.解题思路
         *  3.Python代码

### 0.回文字符串 ###

回文的意思是正着念和倒着念一样，如：**上海自来水来自海上**  
*人中柳如是*  
*是如柳中人*  
*楼望海海望楼  
水连天天连水*

### 1.原文题目 ###

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

示例1

> 输入: “babad”  
> 输出: “bab”  
> 注意: “aba” 也是一个有效答案。

示例2

> 输入: “cbbd”  
> 输出: “bb”

### 2.解题思路 ###

> 思路1  
> 中心扩展：  
> 把每个字母当成回文串的中心  
> 这里要考虑两种情况，回文串的长度为奇数或者偶数情况。

> 思路2  
> 把每个字母当成回文串的结束。

> 思路3  
> dp\[i\]\[j\] 表示字符串从 j 到 i 是否是为回文串，即当 s\[j\] == s\[i\] 如果 dp\[i-1\]\[j+1\] 也是回文串，那么字符串从 j 到 i 也是回文串，即 dp\[i\]\[j\] 为真。

### 3.Python代码 ###

# -*- coding: utf-8 -*- 
    # @Time : 2019/5/17 12:48 
    # @Author : ZXL 
    # @Site :  
    # @File : 5.最长回文字符串.py 
    # @Software: PyCharm
    
    # 中心扩展法
    class Solution1:
        def longestPalindrome(self, s):
            n = len(s)
            self.strhui = ''
            #函数里面定义一个函数
            def July(i, j):
                while i>=0 and j<n and s[i]==s[j] :
                    i -= 1
                    j += 1
                #if语句中的j,i是while里面运行后的
                if len(self.strhui) < j-i-1 :
                    self.strhui = s[i+1 : j]
            for i in range(n):
                #回文数为偶数和奇数
                July(i,i)
                July(i,i+1)
            return self.strhui
    print(Solution1().longestPalindrome('145541526'))
    
    # 把每个字母当成回文串的结束
    class Solution2:
        def longestPalindrome(self, s):
            max_len = 1
            start = 0
            n = len(s)
            # 遍历每一个字符，并假设为回文数的尾字符
            for i in range(1, n):
                # 偶数取序号i前面 max_len个字符，奇数取i前面max_len+1个字符。i+1表示取到序号i字符
                even = s[i - max_len: i + 1]
                odd = s[i - max_len - 1: i + 1]
                # 1 判断 取到的字数组下标，并且是回文数
                # 2 给start赋值，奇数字串max_len加2,偶数字串max_len加1
                if i - max_len >= 0 and even == even[::-1]:
                    start = i - max_len
                    max_len += 1
                elif i - max_len - 1 >= 0 and odd == odd[::-1]:
                    start = i - max_len - 1
                    max_len += 2
    
            return s[start:start + max_len]
    print(Solution2().longestPalindrome('145541526'))