精选50题之 5. 最长回文子串

た入场券 2024-04-17 15:26 7阅读 0赞

### 腾讯精选练习（50 题）之 5. 最长回文子串 ###

*   *  原题目链接
     *  题目分析 v1.0
     *  解题思路 v1.0
     *  代码实现 v1.0
     *  题目分析 v2.0
     *  其他几种算法
     *  写在最后

## [原题目链接][Link 1] ##

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

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

示例 2：  
输入: “cbbd”  
输出: “bb”

## 题目分析 v1.0 ##

小插曲：看到题目的第一反应是使用堆栈…然后看清是不定长度的回文字符子串，瞬间打消念头。

（回到正题）  
分析的结果…回文是正中的字符只有一个（奇数回文串）/两字符相同（偶数回文串），其余字符相较于正中字符对应相同。  
所以可以在一个二维数组中，标记出任意两字符是否相等，然后再查找最长项。——暴力求解

## 解题思路 v1.0 ##

在二维数组的上三角中循环比较，判断子串是不是回文，并最后返回最长的回文子串。其中特别的，对应位置相等可以通过数组中间元素 *右上对角线* 上的元素值进行判断。

## 代码实现 v1.0 ##

python3 实现

class Solution:
        def longestPalindrome(self, s: str) -> str:
            L = len(s)  
            sMatrix = [[0 for i in range(L)] for i in range(L)]
            MaxSubStr = ''
            MaxLen = 0
            
            for j in range(0, L):
                for i in range(0, j+1):
                    
                    if j-i <= 1:
                        if s[i] == s[j]:
                            sMatrix[i][j] = 1
                            if MaxLen < j - i + 1:
                                MaxSubStr = s[i:j+1]
                                MaxLen = j - i + 1
                    
                    else:
                        if s[i] == s[j] and sMatrix[i+1][j-1]: # 左上对角线
                            sMatrix[i][j] = 1
                            if MaxLen < j - i + 1:
                                MaxSubStr = s[i:j+1]
                                MaxLen = j - i + 1
                                
            return MaxSubStr

运行结果  
![v1.0][]  
6秒钟的计算时间，惨不忍睹，毕竟时间复杂度是O(nˆ3)。  
所以优化…

代码优化  
参考：https://blog.csdn.net/qq\_17550379/article/details/84022845

class Solution:
       	def longestPalindrome(self, s: str) -> str:
           	if not s:
               	return ""
    
           	s_len = len(s)
           	mem = [[0]*s_len for _ in range(s_len)]
           	left, right, result_len = 0, 0, 0
           	for j in range(s_len):
               for i in range(j):
                   if s[i] == s[j] and (j-i < 2 or mem[i+1][j-1]):
                       mem[i][j] = 1
                   if mem[i][j] and result_len < j-i+1:
                       result_len = j - i + 1
                       left, right = i, j
               
               mem[j][j] = 1
    
           return s[left:right+1]

![在这里插入图片描述][20190827221709925.png]  
运行速度虽有所提高，但复杂度不变，只能算是代码简化。

其实v1.0已经包含了动态规划的思想，之所以没有实现O(n^2)量级，是因为只是形式上 *像是* 完成了DP的前半部分最优子结构的判断（其实没有），也没有递归求解。我好南啊  
动态规划回顾：  
[漫画版][Link 2]  
[知乎版][Link 3]

## 题目分析 v2.0 ##

待续…

## 其他几种算法 ##

中心扩展算法 [参考][Link 4]

class Solution:
        def longestPalindrome(self, s: str) -> str:
    		if len(s) < 2 or s == s[::-1]:
                return s
            
            start, maxlength = 0, 1
            for i in range(len(s)):
                odd = s[i-maxlength-1:i+1]
                even = s[i-maxlength:i+1]    
                if i-maxlength-1 >= 0 and odd == odd[::-1]:
                    start = i-maxlength-1
                    maxlength += 2
                elif i-maxlength >= 0 and even == even[::-1]:
                    start = i-maxlength
                    maxlength += 1
            return s[start:start+maxlength]

中心扩展算法魔改优化版 [参考][Link 4]

Manacher Algorithm(马拉车算法)

class Solution:
        def longestPalindrome(self, s: str) -> str:
            if s=="":return ""
            s1 = '$#'+'#'.join(s)+'#@'
            mx = 0#已遍历的最大右边界
            mid = 0#对应的中心点
            l = len(s1)
            dp = [0]*l
            for i in range(1,l-1):
                if i<mx:#可以利用之前保存的值
                    dp[i] = min(mx-i,dp[mid*2-i])#不能超过已遍历的右边界
                t = 0
                while 1:#继续扩张
                    if s1[i+dp[i]+t]!=s1[i-dp[i]-t]:
                        break
                    t+=1
                dp[i]+=t-1
                if i+dp[i]>mx:#更新边界值
                    mx = i+dp[i]
                    mid = i
            maxlen,maxidx=0,0
            for i in range(l):#找最大子串
                if dp[i]>maxlen:
                    maxlen = dp[i]
                    maxidx = i
            return s1[maxidx-maxlen:maxidx+maxlen+1].replace('#',"")

## 写在最后 ##

我太南了 我太菜了 继续学习?

[Link 1]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[v1.0]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/49bdd0ad07b74b9a8c982eb359495ae2.png
[20190827221709925.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/0cfec8a6f96a42968240ef2f1ba0b3ba.png
[Link 2]: https://www.sohu.com/a/153858619_466939
[Link 3]: https://www.zhihu.com/question/23995189/answer/35429905
[Link 4]: https://blog.csdn.net/qq_17550379/article/details/84022845