Problem: 5. 最长回文子串
[TOC]
思路
看到题目找最长的回文子串，第一想法就是暴力求解。
用一个first指标定位字符串头，然后从first+1位置开始向后探测
解题方法
python本身提供了[::-1]用于字符串转置，因此通过start位置和游标之间的字符串，用[:]进行拆分后,判断字符串是否为回文串。
这里使用了max_length临时保存最长字符串，并在while循环中避免重复的循环。
复杂度
添加时间复杂度, 示例： 
添加空间复杂度, 示例： 
Code
class Solution:
def longestPalindrome(self, s: str) -> str:
start_index = 0
end_index = len(s)
max_length = 0
flag_start = 0
flag_end = 0
if len(s) == 1:
return s
while start_index max_length:
for cursor in range(0,len(s)+1):
if s[start_index:cursor] == s[start_index:cursor][::-1]:
if cursor-start_index > max_length:
max_length = cursor-start_index
flag_start = start_index
flag_end = cursor
start_index = start_index + 1
return (s[flag_start:flag_end])
[优化]
中心扩散算法
后面看了中心扩散算法对这种回文串的判定的优化算法，可以对n^2的最差情况进行时间复杂度的优化。
中心扩散算法相当于是让字符串向两边进行扩散探测，而上面讲到的这个方法有且只能向后探测，因此需要增加一个游标向前探测。
解题方法
仔细研究了一下中心扩散算法，其实我的算法略作优化效率上也是能达到差不多的效果的。
中心扩散算法中保留了一个max_length，如果max_length已经定义，那么查找最长串的时候，可以直接从mid_cursor往两边各走max_length个长度开始查找回文串。
复杂度
添加时间复杂度, 示例： 
添加空间复杂度, 示例：
Code
class Solution:
def longestPalindrome(self, s: str) -> str:
start_index = 0
end_index = len(s)
max_length = 0
flag_start = 0
flag_end = 0
if len(s) == 1:
return s
while start_index max_length:
for cursor in range(max_length,len(s)+1):
if s[start_index:cursor] == s[start_index:cursor][::-1]:
if cursor-start_index > max_length:
max_length = cursor-start_index
flag_start = start_index
flag_end = cursor
start_index = start_index + 1
return (s[flag_start:flag_end])
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
