Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串（上）
Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串（上）
从下午三点半到晚上十二点，一直卡在这个题，郁闷。经过好几番尝试后，用暴力法完成并提交了一版代码，测试结果超出时间限制。根据反馈的测试用例，专门针对特例做了下处理，才勉强通过测试。
在优化时，参考推荐的“马拉车算法”（Manacher 算法），真的是深深的挫败感。原本盘算着消化理解后再来完成这篇文，奈何琢磨大半天了还没全弄明白。没辙，先记下，后续再慢慢消化吧。
题目
中文题目
第 5 题 无重复字符的最长子串：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
输入: "cbbd"
输出: "bb"英文题目
Question 5 Longest Palindromic Substring: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"思路
最初我是觉得暴力、遍历循环这样解决肯定是不可取的，但是琢磨半天也没能想到好方法，只好就按照回文的规则来逐个暴力尝试了。
其中遇到比较烦恼的点是当重复字符出现在回文中间时，很容易就会破坏设计的规则。所以我决定先把位于子串最中心的重复字符给拿到。比如 "abbcccbba" 中，我要把最中心的 "ccc" 坐标拿到，这样向左、向右来逐个字符检测，直到到头、或者两边字符不匹配。
我是对每个字符遍历，先判断该字符后续有无连续出现相同字符，如果有的话把重复出现的字符合并，然后假定该字符为回文中心点，向左向右检测是否相同来生成以该字符为中心的最长回文串，最终来返回最长的结果。
代码
class Solution:
def longestPalindrome(self, s: str) -> str:
l = len(s)
dic = {}
result = {}
# 获取字符串中每个字符所出现过的坐标
for i,c in enumerate(s):
dic.setdefault(c,[]).append(i)
#print(dic)
# 遍历字符串
for i,c in enumerate(s):
# start 为该字符左侧坐标
start = i-1
# start 为该字符右侧坐标
ending = i+1
# 如果左右两侧与该字符相同，将左右两侧的坐标更新
while start in dic[c]:
start -= 1
while ending in dic[c]:
ending += 1
# 将该重复字符串添加到结果中
result[i]=s[start+1:ending]
# 对左右两侧的字符进行比较
while start>-1 and ending<l:
if s[start]==s[ending]:
# 如果两侧字符相同，更新结果中回文字符的记录
result[i]=s[start:ending+1]
else:
break
start-=1
ending+=1
#print(result)
# 对我们记录所有回文字符串的 result 字典进行遍历，拿到最长的结果返回
max_l = 0
output = s[0] if len(s)>0 else ""
for k,v in result.items():
max_l = len(v) if len(v)>max_l else max_l
if max_l == len(v):
output = v
return output提交答案
提交答案后，结果是“超出时间限制”，原因是有个测试用例是拿长度为 1000的 "bbb…b" 来做的测试，结果我代码运行时间太长了。我在自己的代码中尝试对这个字符串进行处理，是可以拿到正确结果的，只是时间久了些。为了让代码通过，我专门对这种全重复字符的字符串进行额外处理：
# 将该字符串转化为集合
c_set = set(s)
# 如果集合中只有一个元素，直接返回这个字符串
if len(c_set)==1:
return s有了这个单独处理，勉强通过了测试。
中文区结果：
执行用时 :9856 ms ms, 在所有 Python3 提交中击败了5.04%的用户 内存消耗 :14.2 MB, 在所有 Python3 提交中击败了15.00%的用户
英文版结果：
Runtime: 8220 ms, faster than 6.10% of Python3 online submissions for Longest Palindromic Substring. Memory Usage: 14.3 MB, less than 17.65% of Python3 online submissions for Longest Palindromic Substring.
意料之中，在尝试了几个其它思路后，投降，开始翻看评论区中的 Manacher 算法。但直到现在也没能完全吃透。
结论
第五题，暴力破解法仍有提升空间，推荐的专门针对回文的马拉车算法也还没有吃透，明天继续完善关于这个题目的算法解析吧。
好难。。。