題目：
給定一個(gè)字符串 s税肪，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000斩披。鏈接
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案产禾。
示例 2：
輸入: "cbbd"
輸出: "bb"
動(dòng)態(tài)規(guī)劃標(biāo)簽下頻率最高的題目潦闲。
解題過程
暴力解法
沒太多好說的，復(fù)雜度O(N3)哨免，Swift不會(huì)超時(shí)茎活，Python超時(shí)。
Swift:
class Solution {
func longestPalindrome(_ s: String) -> String {
let count = s.count
if count < 2 { return s }
// 記錄子串起始位置
var range = (0, 0)
let sArr = Array(s)
for i in 0..<count-1 {
for j in i+1..<count {
// 優(yōu)先判定當(dāng)前的子串長(zhǎng)度是否是最長(zhǎng)的琢唾，以便減少計(jì)算
if j - i > range.1 - range.0 && isPalindrome(sArr, range: (i, j)) {
range = (i, j)
}
}
}
return String(sArr[range.0...range.1])
}
func isPalindrome(_ sArr: [String.Element], range: (Int, Int)) -> Bool {
var left = range.0, right = range.1
while left < right {
if sArr[left] != sArr[right] {
return false
}
left += 1
right -= 1
}
return true
}
}
Python3:
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
begin = 0
end = 0
for i in range(size - 1):
for j in range(1, size):
if j - i > end - begin and self.__isPalindrome(s, i, j):
begin = i
end = j
return s[begin:end+1]
def __isPalindrome(self, s, left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
動(dòng)態(tài)規(guī)劃方法
動(dòng)態(tài)規(guī)劃的一般思考方法：
- 定義狀態(tài)
- 思考狀態(tài)轉(zhuǎn)移方程
- 確定邊界
- 結(jié)果輸出
針對(duì)當(dāng)前題目來講载荔，可以把狀態(tài)設(shè)為范圍子串是否為回文子串，用一張二維表來表示慧耍，即行(i)為子串左側(cè)范圍身辨，列(j)為子串右側(cè)范圍丐谋，值為是否回文芍碧。
之后需要思考狀態(tài)轉(zhuǎn)移方程号俐，根據(jù)回文子串的定義泌豆，可以知道最左側(cè)和最右側(cè)的字符必須相同，至于子串是否相同則交給dp來判斷吏饿，所以我們可以得出轉(zhuǎn)移方程如下：
dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
以此可以知道踪危，當(dāng)s[i] == s[j]時(shí)，字符串是否回文是由子串是否回文決定的猪落，進(jìn)一步就要思考dp的邊界值來初始化dp基礎(chǔ)值贞远。
還是通過回文字符串的定義來看，當(dāng)字符串的長(zhǎng)度為1時(shí)笨忌，該字符串必定回文蓝仲。那么可以得出公式：
if j - i + 1 < 2 && j - 1 - (i + 1) + 1 < 2 {
dp[i][j] = true
}
簡(jiǎn)化為：
if j - i < 3 {
dp[i][j] = true
}
至此，已經(jīng)推斷出動(dòng)態(tài)規(guī)劃所需的大部分條件官疲，我們要考慮怎樣使用這些條件輸出期望的結(jié)果袱结。
如果需要確定子串？是否回文途凫，依賴的是它的最大子串垢夹，即(1, 4)是否回文，這就涉及到一個(gè)概念無后效性维费，無后效性是動(dòng)態(tài)規(guī)劃的一個(gè)必須條件果元，動(dòng)態(tài)規(guī)劃是典型的空間換時(shí)間，要想知道當(dāng)前狀態(tài)的值犀盟，必須知道前置狀態(tài)的值而晒，所以前置狀態(tài)必須提前計(jì)算出來，這就是所謂的無后效性且蓬。
根據(jù)當(dāng)前題目中的狀態(tài)定義欣硼，要知道一個(gè)指，必須依賴它左下角的值，所以我們遍歷二維表的時(shí)候诈胜，需要先經(jīng)過(1, 4)再到(0, 5)豹障。以下舉兩個(gè)例子：
- 按照順序1的循環(huán)結(jié)構(gòu)：
for j in 1..<count {
for i in 0..<j { ... }
}
- 按照順序2的循環(huán)結(jié)構(gòu)：
for i in (0..<count).reversed() {
for j in i..<count { ... }
}
至于遍歷順序的選擇，只要滿足無后效性的條件焦匈，效率上差別并不是太大⊙現(xiàn)在動(dòng)態(tài)規(guī)劃問題思考的四個(gè)步驟都已經(jīng)完成，完整代碼如下：
Swift:
class Solution {
func longestPalindrome(_ s: String) -> String {
let count = s.count
if count < 2 { return s }
// 定義狀態(tài)缓熟，dp[i][j]表示字符串下標(biāo)i...j的子串
var dp = [[Bool]]()
for _ in 0..<count {
dp.append(Array(repeating: false, count: count))
}
let sArr = Array(s)
var range = (0, 0)
// 狀態(tài)轉(zhuǎn)移方程：dp[i][j] = sArr[i] == sArr[j] && dp[i + 1][j - 1]
for j in 1..<count {
for i in 0..<j {
// 方程第一個(gè)條件
if sArr[i] == sArr[j] {
// 邊界條件：子串長(zhǎng)度 < 2累魔，則必定是回文
if j - 1 - (i + 1) + 1 < 2 {
dp[i][j] = true
} else {
// 方程第二個(gè)條件
dp[i][j] = dp[i + 1][j - 1]
}
} else {
dp[i][j] = false
}
// 考慮輸出
if dp[i][j] && j - i > range.1 - range.0 {
range = (i, j)
}
}
}
return String(sArr[range.0...range.1])
}
}
Python3:
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
dp = [[False for _ in range(size)] for _ in range(size)]
begin = 0
end = 0
for j in range(1, size):
for i in range(0, j):
# 轉(zhuǎn)移方程：dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
if s[i] == s[j]:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = False
if dp[i][j] and j - i > end - begin:
begin = i
end = j
return s[begin:end+1]
中心擴(kuò)散方法
充分利用回文字符串的特性，可以將一個(gè)回文字符串分為中心區(qū)域+兩側(cè)區(qū)域够滑，中心區(qū)域為相同的字符組成垦写，兩側(cè)區(qū)域由對(duì)應(yīng)相同的字符組成，即為回文字符串彰触。
不需要關(guān)心中心區(qū)域到底有多少字符梯投，只要是相同的字符組成的必然是回文的，在此基礎(chǔ)上盡可能地向兩側(cè)擴(kuò)展况毅。
查找中心區(qū)域
while end + 1 < count && sArr[start] == sArr[end + 1] {
end += 1
}
擴(kuò)展兩側(cè)區(qū)域
while start - 1 >= 0 && end + 1 < count && sArr[start - 1] == sArr[end + 1] {
start -= 1
end += 1
}
提高效率的核心做法就是把循壞快進(jìn)分蓖，當(dāng)查到核心區(qū)域的邊界時(shí)，下一次循環(huán)直接從邊界位置的下一個(gè)開始即可尔许。
完整代碼如下：
Swift:
class Solution {
func longestPalindrome(_ s: String) -> String {
let count = s.count
if count < 2 { return s }
let sArr = Array(s)
var range = (0, 0)
var begin = 0
while begin < count - 1 {
var end = begin
// 找出中心區(qū)域么鹤，后面進(jìn)行快進(jìn)操作
while end + 1 < count && sArr[begin] == sArr[end + 1] {
end += 1
}
let tmp = end
// 從中心區(qū)域向兩側(cè)進(jìn)行擴(kuò)散
while begin - 1 >= 0 && end + 1 < count && sArr[begin - 1] == sArr[end + 1] {
begin -= 1
end += 1
}
// 輸出值
if end - begin > range.1 - range.0 {
range = (begin, end)
}
// 開始快進(jìn)
begin = tmp + 1
}
return String(sArr[range.0...range.1])
}
}
Python3:
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
loc = [0, 0]
begin = 0
while begin < size - 1:
end = begin
while end + 1 < size and s[end + 1] == s[begin]:
end += 1
tmp = end
while begin - 1 >= 0 and end + 1 < size and s[begin - 1] == s[end + 1]:
begin -= 1
end += 1
if end - begin > loc[1] - loc[0]:
loc[0] = begin
loc[1] = end
begin = tmp + 1
return s[loc[0]:loc[1] + 1]
因?yàn)閯?dòng)態(tài)規(guī)劃方法說到底還是屬于暴力解法，所以效率上肯定要比題目特定的優(yōu)化解法慢味廊，不過動(dòng)規(guī)思路更為通用蒸甜，此篇也更多為了讓自己進(jìn)一步理解，希望對(duì)你也有所幫助毡们。
以下也可以用中心擴(kuò)散的思想來判定回文：
125. 驗(yàn)證回文串
