題目
給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串剩蟀。你可以假設(shè) s 的最大長(zhǎng)度為 1000。
示例
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
解答
方案1：暴力求解
遍歷每一個(gè)子串，構(gòu)建回文串判定函數(shù)（is_palindromic_string）钧萍，用于判定每個(gè)子串是否為回文串，隨時(shí)更新當(dāng)前最大回文子串（max_substr）及其長(zhǎng)度（max_len）政鼠。
class Solution:
def longestPalindrome(self, s):
is_palindromic_string = lambda s: s == s[::-1] # 回文串判定函數(shù)
max_len, max_substr = 0, ''
for i in range(len(s)):
for j in range(i+1, len(s)+1):
cur_substr = s[i:j] # 取當(dāng)前子串
print(cur_substr)
if is_palindromic_string(cur_substr):
cur_len = len(cur_substr) # 當(dāng)前子串長(zhǎng)度
if cur_len > max_len:
max_len = cur_len
max_substr = cur_substr # 當(dāng)前最長(zhǎng)子串
return max_substr
算法的時(shí)間復(fù)雜度為O(N^3)风瘦，果然，時(shí)間超過(guò)限制缔俄。
方案2：動(dòng)態(tài)規(guī)劃
這里弛秋，我們采用以空間換時(shí)間的動(dòng)態(tài)規(guī)劃策略器躏，網(wǎng)上很多案例晦澀難懂俐载，我們這里稍作改造。設(shè)我們的輸入字符串為s：
1.構(gòu)造二維矩陣dp登失，維度為len(s)*len(s)遏佣，dp[left][right]表示子串s[left:right+1]是否為回文串，left和right均為下標(biāo)索引揽浙，范圍在0~len(s)之間状婶，且left<right意敛，因此dp矩陣中的每一個(gè)變量均為布爾量；
2.構(gòu)造狀態(tài)轉(zhuǎn)移方程膛虫，考慮三種情況草姻，
（1）left = right，當(dāng)前子串只有一個(gè)字符稍刀，一定為回文串撩独；
（2）right = left + 1，當(dāng)前子串只有兩個(gè)字符账月，判斷這兩個(gè)字符是否相等综膀；
（3）right > left + 1，當(dāng)前子串有多個(gè)字符局齿，判斷根據(jù)首位字符是否相等以及除去首位字符剩余子串是否為回文串判定當(dāng)前子串剧劝。
狀態(tài)轉(zhuǎn)移方程為：
或者把前兩種情況歸類：
class Solution:
def longestPalindrome(self, s):
dp = [[False]*len(s) for _ in range(len(s))]
max_start, max_len = 0, 0 # 最長(zhǎng)回文子串開(kāi)始位置及長(zhǎng)度
for right in range(len(s)): # 右指針先走
for left in range(right+1): # 左指針跟著右指針
if right - left < 2: # 前兩種情況
dp[left][right] = (s[left] == s[right])
else: # 最后一種情況
dp[left][right] = (s[left] == s[right]) and dp[left+1][right-1]
# cur_substr = s[left:right+1] # 當(dāng)前考察的子串
cur_len = right + 1 - left # 當(dāng)前子串長(zhǎng)度為 right + 1 - left
if dp[left][right] and max_len < cur_len:
max_start = left
max_len = cur_len
return s[max_start:max_start + max_len]
時(shí)間和空間復(fù)雜度O(N^2)，通過(guò)了驗(yàn)證抓歼，但是這個(gè)程序還是比較慢的：
執(zhí)行用時(shí) : 8980 ms, 擊敗了7.80% 的用戶
內(nèi)存消耗 : 20.7 MB, 中擊敗了17.62% 的用戶
方案3：中心擴(kuò)展
回文串有兩個(gè)特點(diǎn)：
1.當(dāng)回文串的左側(cè)和右側(cè)同時(shí)增加相同的字符時(shí)讥此，構(gòu)成的字符串也是回文串；
2.只有一個(gè)字符的字符串本身也是回文串谣妻；
根據(jù)這個(gè)特點(diǎn)暂论，我們從頭到尾遍歷字符串，并且每遍歷到一個(gè)位置時(shí)拌禾，我們都對(duì)這個(gè)位置的字符進(jìn)行左右擴(kuò)展取胎，如果左右兩頭的元素相同，又可以構(gòu)成新的回文子串湃窍，循環(huán)執(zhí)行下去闻蛀，直到左右兩端元素不相同了為止，在此過(guò)程中您市，記錄下每次擴(kuò)展得到的最長(zhǎng)子串起始位置和長(zhǎng)度觉痛。需要注意的是，根據(jù)回文子串元素個(gè)數(shù)茵休，我們需要考慮兩種情況薪棒，一種是奇數(shù)個(gè)，一種是偶數(shù)個(gè)榕莺，這里我們用左右擴(kuò)展的起始下標(biāo)進(jìn)行區(qū)分俐芯。
class Solution:
def longestPalindrome(self, s):
def extend(start_idx, end_idx, max_start, max_len):
"""
擴(kuò)展函數(shù)，用于得到向左向右同步擴(kuò)展后的最長(zhǎng)回文子串
:param start_idx: 向左擴(kuò)展的起始位置
:param end_idx: 向右擴(kuò)展的起始位置
:param max_start: 當(dāng)前最長(zhǎng)回文子串的左指針
:param max_len: 當(dāng)前最大長(zhǎng)度
:return: 當(dāng)前最長(zhǎng)回文子串的起始位置和長(zhǎng)度
"""
while 0 <= start_idx <= end_idx < len(s): # 子串起止下標(biāo)合法時(shí)
if s[start_idx] == s[end_idx]: # 如果新增的兩端字符相等
cur_str = s[start_idx:end_idx] # 當(dāng)前子串是回文串
cur_len = end_idx + 1 - start_idx # 當(dāng)前子串長(zhǎng)度
if max_len < cur_len:
max_len = cur_len
max_start = start_idx
start_idx -= 1 # 左指針向左移動(dòng)一位
end_idx += 1 # 右指針向右移動(dòng)一位
else:
break
return max_start, max_len
max_start, max_len = 0, 0 # 初始化最長(zhǎng)回文子串開(kāi)始位置及長(zhǎng)度
for i in range(len(s)): # 進(jìn)行一次遍歷
left = right = i # 判斷長(zhǎng)度為奇數(shù)的回文子串開(kāi)始和結(jié)束位置
# 從i位置向兩邊擴(kuò)展钉鸯，搜尋可以得到的最大回文子串
max_start, max_len = extend(left, right, max_start, max_len)
left, right = i, i+1 # 判斷長(zhǎng)度為偶數(shù)的回文子串開(kāi)始和結(jié)束位置
# 從i位置向左擴(kuò)展吧史，從i+1位置向右擴(kuò)展，搜尋可以得到的最大回文子串
max_start, max_len = extend(left, right, max_start, max_len)
return s[max_start:max_start + max_len]
網(wǎng)上廣為流傳的還有一個(gè)辦法唠雕，遍歷字符串中每一個(gè)字符贸营，主要考慮兩種情況：
- 向左和向右各擴(kuò)展一個(gè)字符吨述，查看構(gòu)成的新子串是否為回文串；
- 只向右擴(kuò)展一個(gè)字符钞脂，查看構(gòu)成的新子串是否為會(huì)問(wèn)串揣云。
這種方法要更加快些。
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
is_palindromic_string = lambda s: s == s[::-1]
str_length = len(s)
cur_length = 0
start_index = 0
for i in range(str_length):
cur_start_index = i - cur_length - 1 # 向左擴(kuò)展一個(gè)字符
cur_substr = s[cur_start_index: cur_start_index+cur_length+2] # 向右擴(kuò)展一個(gè)字符冰啃，獲得子串
if cur_start_index >= 0 and is_palindromic_string(cur_substr): # 判斷擴(kuò)展后的子串是否回文
start_index = cur_start_index # 更新子串起始下標(biāo)
cur_length += 2 # 更新當(dāng)前最長(zhǎng)子串長(zhǎng)度
else:
cur_start_index = i - cur_length # 向左不擴(kuò)展
cur_substr = s[cur_start_index: cur_start_index+cur_length+1] # 向右擴(kuò)展一個(gè)字符灵再，獲得子串
if cur_start_index >= 0 and is_palindromic_string(cur_substr): # 判斷擴(kuò)展后的子串是否回文
start_index = cur_start_index # 更新子串起始下標(biāo)
cur_length += 1 # 更新當(dāng)前最長(zhǎng)子串長(zhǎng)度
return s[start_index: start_index + cur_length]
其實(shí)還有疑問(wèn)，為什么當(dāng)兩邊擴(kuò)展后就無(wú)需單邊擴(kuò)展亿笤，以及為何起始下標(biāo)要這樣設(shè)置翎迁，懂的大佬請(qǐng)?jiān)谠u(píng)論中留言。净薛。
執(zhí)行用時(shí) : 92 ms, 擊敗了96.52% 的用戶
內(nèi)存消耗 : 13 MB, 擊敗了94.22% 的用戶
方案4：Manacher's Algorithm（馬拉車算法）
我們可以看到上面需要考慮子串是長(zhǎng)度為奇數(shù)還是偶數(shù)兩種情況汪榔，如何可以統(tǒng)一起來(lái)？馬拉車算法應(yīng)運(yùn)而生肃拜。我們?cè)谳斎胱址谩?”隔開(kāi)痴腌，且首位也添加“#”號(hào)，如“cbbcd”變成“#c#b#b#c#d#”燃领，這樣就可以確保字符串的長(zhǎng)度為奇數(shù)了士聪。
class Solution:
def longestPalindrome(self, s):
def get_length(string, index):
# 循環(huán)求出index為中心的最長(zhǎng)回文字串
start, length = index // 2, 0
r_ = len(string)
for i in range(1, index + 1):
if index + i < r_ and string[index - i] == string[index + i]:
start = (index - i) // 2
length += 1
else:
break
return start, length
s_list = [c for c in s]
new_s = '#' + '#'.join(s_list) + '#' # 形成新串
max_start = max_length = 0
length = len(new_s)
for index in range(0, length):
start, r_length = get_length(new_s, index)
if max_length < r_length:
max_start, max_length = start, r_length
return s[max_start: max_start+max_length]
如有疑問(wèn)，歡迎評(píng)論區(qū)留言~
