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）
完整代码运行结果如下：（小詹是中文网站看题，英文网站提交）
