春衣少年当酒歌,起舞四顾以笑和。这篇文章主要讲述#yyds干货盘点#马拉车算法解最长回文子串!Manacher相关的知识,希望能为你提供帮助。
文章图片
这是我参与11月更文挑战的第11天。
一、写在前面
LeetCode 第一题两数之和传输门:听说你还在写双层for循环解两数之和?
LeetCode 第二题两数之和传输门:两个排序数组的中位数,“最”有技术含量的解法!
今天给大家分享的是LeetCode 数组与字符串 第三题:最长回文子串,为面试而生,期待你的加入。
二、今日题目
给定一个字符串 s,找到 s 中最长的回文子串。
你可以假设 s 的最大长度为1000。
示例:
示例 1:输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。示例 2:输入: "cbbd"
输出: "bb"
三、 分析
这个题目呢,之前参加校IT精英赛时遇到过,当时用c写的,呃···可惜,没写出来,所以咋看第一眼,有点心凉的感觉,当然今日之我已非彼时,早已深知回文字符是个啥玩意,比如日期:2018102,就是个回文字符串。
我是这样想的,要找字符串中最长的回文字符串,肯定就要先找出这个字符串的子串中那些是回文串,然后再求他们中最长的,就可以找到答案了,理清思路,我就开始兴奋的敲代码了,然而...
四、解题
- 方法一:
根据上面的思路,一步步来,时间复杂度,嗯,好像有O(n^4)...class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ len_s = len(s) if len_s == 1: return s substring = substring_set = [] for i in range(len_s): for j in range(len_s): if i < j : substring = s[i:j+1] if self.is_Palindrome(substring) == 1: substring_set.append(substring) longest_s = if substring_set: longest_s = substring_set[0] else: return s[0] for i in range(len(substring_set) - 1): if len(longest_s) < len(substring_set[i + 1]): longest_s = substring_set[i + 1] return longest_s # 判断是否为回文字符 def is_Palindrome(self,str_t): len_t = len(str_t) for i in range(len_t): if not str_t[i] == str_t[len_t - 1 - i]: return 0 return 1 s = assas s0 = Solution() l_Palindrome = s0.longestPalindrome(s) print(l_Palindrome)
- 提交结果:
文章图片
- 方法二:
对于方法一,无话可说,思前想后,没个结果,百度,嗯,百度是个好东西。
从从中心向外扩散,时间复杂度:O(n^2)
文章图片
思想参考:https://blog.csdn.net/qq_32354501/article/details/80084325
原作者用java实现class Solution:
# 类变量,类全局可调用
longest_s =# 最长回文字符串
maxLen = 0# 长度def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
len_s = len(s)
if len_s == 1:# 单字符串
return s
for i in range(len_s):
# 单核(奇数向两边延伸)
self.find_longest_Palindrome(s, i, i)
# 双核(偶数向两边延伸)
self.find_longest_Palindrome(s, i, i + 1)
return self.longest_s# 找出最长的回文字符串
def find_longest_Palindrome(self, s, low, high):
# 从中间向两端延伸,判断是否为回文字符串的同时寻找最长长度
while low >
= 0 and high <
len(s):
if s[low] == s[high]:
low -= 1# 向左延伸
high += 1# 向右延伸
else:
break
# high - low - 1 表示当前回文字符串长度
if high - low - 1 >
self.maxLen:
self.maxLen = high - low - 1
self.longest_s = s[low + 1:high]
- 提交结果
文章图片
- 方法三:
Manacher算法
算法只有遇到还没匹配的位置时才进行匹配,已经匹配过的位置不再进行匹配,因此大大的减少了重复匹配的步骤,对于S_new中的每个字符只进行一次匹配。所以该算法的时间复杂度为O(2n+1)—> O(n)(n为原字符串的长度),所以其时间复杂度依旧是线性的。
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
t0 = #.join(s)
s_new = # + t0 + #
len_new = []
sub =# 最长回文字符串
sub_midd = 0# 表示在i之前所得到的Len数组中的最大值所在位置
sub_side = 0# 表示以sub_midd为中心的最长回文子串的最右端在S_new中的位置
for i in range(len(s_new)):
if i <
sub_side :
# i <
sub_side时,在Len[j]和sub_side - i中取最小值,省去了j的判断
j = 2 * sub_midd - i
if j >
= 2 * sub_midd - sub_side andlen_new[j] <
= sub_side - i:
len_new.append(len_new[j])
else:
len_new.append(sub_side - i + 1)
else:
# i >
= sub_side时,从头开始匹配
len_new.append(1)
while ((i - len_new[i] >
= 0 and i + len_new[i] <
len(s_new)) and (s_new[i - len_new[i]] == s_new[i + len_new[i]])):
# s_new[i]两端开始扩展匹配,直到匹配失败时停止
len_new[i] = len_new[i] + 1if len_new[i] >
= len_new[sub_midd]:
sub_side = len_new[i] + i - 1
sub_midd = i
a0 = int((2 * sub_midd - sub_side)/2)
b0 = int(sub_side / 2)
sub = s[a0 :b0 ] # 在s中找到最长回文子串的位置
return sub
- 提交结果
文章图片
坚持 and 努力 : 终有所获。
思想很复杂,
实现很有趣,
只要不放弃,
终有成名日。
—《老表打油诗》
下期见,我是爱猫爱技术的老表,如果觉得本文对你学习有所帮助,欢迎点赞、评论、关注我!
推荐阅读
- git基础命令大全
- SpringCloud升级之路2020.0.x版-40. spock 单元测试封装的 WebClie
- #yyds干货盘点#Galang中的map数据类型使用
- #yyds干货盘点# web安全day10(通过实验理解windows域的OU和GPO)
- 并发高(可能是编译优化引发有序性问题)
- 打印日历和当前时间(简单易懂)
- #yyds干货盘点#3. 无转折不编程,滚雪球学 Python
- 作为初学者,物理层与数据链路层要了解哪些
- C# 从 UTF-8 流中读取字符串的正确方法