LeetCode.jpg
5. 最長回文子串
5. 最長回文子串
給定一個字符串 s孵淘，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000歹篓。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案瘫证。
示例 2：
輸入: "cbbd"
輸出: "bb"
切題
一、Clarification
求最長回文子串庄撮，這里有幾個特殊情況需要考慮
1背捌、空字符串， "" 洞斯，最長回文子串 ""
2毡庆、單個字符，"a"烙如，最長回文子串 "a"
3么抗、兩個字符，"ab"亚铁，最長回文子串 "a"或者"b"
兩個字符蝇刀，"cc"， 最長回文子串 "cc"
二徘溢、Possible Solution
1吞琐、暴力求解
從最長字符串開始掃描
2、動態(tài)規(guī)劃
狀態(tài)定義然爆、狀態(tài)轉(zhuǎn)移方程
Python3
暴力求解
# @author:leacoder
# @des: 暴力求解 最長回文子串
'''
從最長字符串開始掃描（最長子串就是其本身）子串個數(shù)為 1站粟，如果不是回文 子串長度-1，子串個數(shù)+1
子串長度 子串個數(shù)
n 1
n-1 2
. .
. .
2 n-1
1 n
'''
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if 0 == n:
return null
for i in range(n): # i = 0 時為最長子串曾雕，長度n 奴烙；i = 1時 子串長度n-1子串個數(shù)2
start = 0
end = n - i # n-i 長度子串中，第一個子串的起始位置
while end <= n:
sub_string = s[start:end] # 子串
# 判斷是否回文
if self.is_palindromic_string(sub_string):
return sub_string
# 遍歷長度為 n-i 的所有子串
start += 1
end +=1
def is_palindromic_string(self,s):
return s == s[::-1]
動態(tài)規(guī)劃
# @author:leacoder
# @des: 動態(tài)規(guī)劃 最長回文子串
'''
動態(tài)規(guī)劃分析
一翻默、狀態(tài)定義
dp[l][r] 表示子串s[l,r] (包括區(qū)間l 和 r, l 表示子串左邊索引缸沃，r 表示子串右邊索引) 是否是回文，也就是如果s[l,r]是回文字符串修械，則有dp[l][r] = true
二趾牧、狀態(tài)轉(zhuǎn)移方程
1、如果s[l+1,r-1]長度大于 1,也就是 r-1 - (l+1)>0 -> r - 1 > 2 時肯污，dp[l+1][r-1]=true 并且 s[l] == s[r] 那么 s[l,r] 為回文字符串 dp[l][r] = true
s[l+1,r-1]為回文字符串翘单，只有當(dāng)s[l] == s[r]時 s[l,r] 才為回文字符串
2吨枉、如果s[l+1,r-1] 長度為 1 也就是 r-1 - (l+1) = 0 -> r - l = 2 時 并且 s[l] == s[r] 那么 s[l,r] 為回文字符串 dp[l][r] = true
3、如果s[l+1,r-1] 為空字符串小于1也就是 r-1 - (l+1)< 0 -> r - l < 2哄芜，并且 s[l] == s[r] 那么 s[l,r] 為回文字符串貌亭，dp[l][r] = true
2 和 3合并為一個條件 r - l <= 2 并且 s[l] == s[r]
所以 綜上狀態(tài)轉(zhuǎn)移方程 為
s[l] == s[r] and (r -1 <= 2 or dp[l + 1, r - 1]) 那么 dp[l, r] = = true
'''
'''
特殊情況
當(dāng)s字符串長度<=1時，其本身必然為回文字符串
'''
class Solution:
def longestPalindrome(self, s: str) -> str:
# 特殊情況
size = len(s)
if size <= 1:
return s
# 狀態(tài) 初始化 dp[l,r] 二維狀態(tài)认臊，初始化為False
dp = [[False for _ in range(size)] for _ in range(size)]
# 最長回文子串
max_length = 0
# max_substring = ""
max_substring = s[0] # 兼容處理 "ab" 這種情況
# <=1 的情況 已在特殊情況中處理
for r in range(1,size):
for l in range(r):
if s[l] == s[r] and (r - l <= 2 or dp[l + 1][r - 1]):
dp[l][r] = True
cur_length = r - l + 1 # 當(dāng)前回文字符串長度
if cur_length > max_length:
max_length = cur_length
max_substring = s[l:r+1] # r+1取不到
return max_substring
GitHub鏈接：
https://github.com/lichangke/LeetCode
個人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學(xué)習(xí)
