拿什么拯救你，我的offer！（从零打卡刷Leetcode——No.005）
拿什么拯救你，我的offer！（从零打卡刷Leetcode——No.005）
写在前边：
小詹此记录贴的读者越来越少了，也许是小詹总结的不够好欢迎留言区提出宝贵的意见！也欢迎和小詹一起定期刷leetcode，每周一和周五更新一题，每一题都吃透，欢迎一题多解，寻找最优解！这个记录帖哪怕只有一个读者，小詹也会坚持刷下去的！
No.5 最大回文子串
原题：（有中文网站，就不去读英语啦哈哈）
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
例如:
#示例一
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
#示例二
输入: "cbbd"
输出: "bb"思路分析：这题难度官网给出的是中等难度，小詹自己做的时候却花了很久，学习之路还有很远啊~看到这个题目，小詹是想着先找到所有存在的回文子串，之后比较长度，输出最长的子串。动笔根据所给案例进行了比划，发现一个很关键的点！最长回文子串的中间子串也是回文串，换言之，回文串是否最长，可以看回文串两边的字符是否相同。例如“dabcba”的最长回文子串是“abcba”，其可看出回文子串“bcb”的拓展，判断“bab”两边的字符是否相同决定是否进行回文子串拓展（可以利用切片的索引左右移动实现）
排坑！小詹觉得这个思路不错，就按照思路进行了实现，代码是下面这样子的（有雷坑噢）
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
#小詹提示：这种题要注意特例，单字符本身就是自己的最大回文子串噢
if len(s) < 2:
return s
#定义待返回的字符串
self.res = ""
for i in range(len(s)):
#遍历假设每一个字符为回文字符中心，向两端拓展判断，left,right,记录字符串左右索引
left = right = i
#这里是判断当前回文子串两端相同的时候，向两端拓展
while left>=0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
#这里的right-left-1是当前的回文子串长度，大于历史最大值，就更新最大值
if right -left -1 > len(self.res):
self.res = s[left+1:right]
return self.res嗯~小伙伴感兴趣可以将代码提交试试看，只能通过部分样例测试。为什么呢？小詹提交后发现类似示例2“cbbd”这种会出错！找到了错误就好分析了，是因为上边的代码默认从同一个字符位置向两端拓展，然而类似“cbbd”这种测试用例，是从相邻两个字符串位置进行拓展，所以我们可以两种情况都考虑进去，最后选择最长的，考虑到这之间有相同的操作，为代码整洁，将其模块化分割出一个函数，代码如下：
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
#小詹提示：这种题要注意特例，单字符本身就是自己的最大回文子串噢
if len(s) < 2:
return s
#定义待返回的字符串
self.res = ""
for i in range(len(s)):
#这里就是考虑到两种情况，从相同字符拓宽和从相邻字符拓宽
self.helper(s, i, i)
self.helper(s, i, i+1)
return self.res
#分割出来的相同操作函数！
def helper(self,s, left, right):
#这里是判断当前回文子串两端相同的时候，向两端拓展
while left>=0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
#这里的right-left-1是当前的回文子串长度，大于历史最大值，就更新最大值
if right -left -1 > len(self.res):
self.res = s[left+1:right]给出运行结果之前，有必要关于self说几句，之前也有小伙伴群里问过，这里给出几句话：
- self 不是一个关键词，可以替换成其他（比如this），只是习惯用self
- self不是指向类本身，而是指向类实例对象（比如class person() a = person('xiaozhan')，这时self会指向实例person类的实例类对象a）
完整代码运行结果如下：（小詹是中文网站看题，英文网站提交）
往期推荐
【记录帖】（No.001）从零打卡刷Leetcode
【记录帖】（No.002）从零打卡刷Leetcode
【记录帖】（No.003）从零打卡刷Leetcode
【记录帖】（No.004）从零打卡刷Leetcode