题目：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。链接
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
动态规划标签下频率最高的题目。
相关企业
解题过程
暴力解法
没太多好说的，复杂度O(N³)，Swift不会超时，Python超时。
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 {
// 优先判定当前的子串长度是否是最长的，以便减少计算
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
动态规划方法
动态规划的一般思考方法：
- 定义状态
- 思考状态转移方程
- 确定边界
- 结果输出
针对当前题目来讲，可以把状态设为范围子串是否为回文子串，用一张二维表来表示，即行(i)为子串左侧范围，列(j)为子串右侧范围，值为是否回文。
状态，标绿代表回文子串
之后需要思考状态转移方程，根据回文子串的定义，可以知道最左侧和最右侧的字符必须相同，至于子串是否相同则交给dp来判断，所以我们可以得出转移方程如下：
dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
以此可以知道，当s[i] == s[j]时，字符串是否回文是由子串是否回文决定的，进一步就要思考dp的边界值来初始化dp基础值。
还是通过回文字符串的定义来看，当字符串的长度为1时，该字符串必定回文。那么可以得出公式：
if j - i + 1 < 2 && j - 1 - (i + 1) + 1 < 2 {
dp[i][j] = true
}
简化为：
if j - i < 3 {
dp[i][j] = true
}
至此，已经推断出动态规划所需的大部分条件，我们要考虑怎样使用这些条件输出期望的结果。
确定子串?是否回文
如果需要确定子串？是否回文，依赖的是它的最大子串，即(1, 4)是否回文，这就涉及到一个概念无后效性，无后效性是动态规划的一个必须条件，动态规划是典型的空间换时间，要想知道当前状态的值，必须知道前置状态的值，所以前置状态必须提前计算出来，这就是所谓的无后效性。
根据当前题目中的状态定义，要知道一个指，必须依赖它左下角的值，所以我们遍历二维表的时候，需要先经过(1, 4)再到(0, 5)。以下举两个例子：
遍历顺序1
- 按照顺序1的循环结构：
for j in 1..<count {
for i in 0..<j { ... }
}
遍历顺序2
- 按照顺序2的循环结构：
for i in (0..<count).reversed() {
for j in i..<count { ... }
}
至于遍历顺序的选择，只要满足无后效性的条件，效率上差别并不是太大。现在动态规划问题思考的四个步骤都已经完成，完整代码如下：
Swift:
class Solution {
func longestPalindrome(_ s: String) -> String {
let count = s.count
if count < 2 { return s }
// 定义状态，dp[i][j]表示字符串下标i...j的子串
var dp = [[Bool]]()
for _ in 0..<count {
dp.append(Array(repeating: false, count: count))
}
let sArr = Array(s)
var range = (0, 0)
// 状态转移方程：dp[i][j] = sArr[i] == sArr[j] && dp[i + 1][j - 1]
for j in 1..<count {
for i in 0..<j {
// 方程第一个条件
if sArr[i] == sArr[j] {
// 边界条件：子串长度 < 2，则必定是回文
if j - 1 - (i + 1) + 1 < 2 {
dp[i][j] = true
} else {
// 方程第二个条件
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):
# 转移方程：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]
效率上Swift高不少
中心扩散方法
充分利用回文字符串的特性，可以将一个回文字符串分为中心区域+两侧区域，中心区域为相同的字符组成，两侧区域由对应相同的字符组成，即为回文字符串。
中心区域和两侧区域
不需要关心中心区域到底有多少字符，只要是相同的字符组成的必然是回文的，在此基础上尽可能地向两侧扩展。
查找中心区域
while end + 1 < count && sArr[start] == sArr[end + 1] {
end += 1
}
扩展两侧区域
while start - 1 >= 0 && end + 1 < count && sArr[start - 1] == sArr[end + 1] {
start -= 1
end += 1
}
提高效率的核心做法就是把循坏快进，当查到核心区域的边界时，下一次循环直接从边界位置的下一个开始即可。
完整代码如下：
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
// 找出中心区域，后面进行快进操作
while end + 1 < count && sArr[begin] == sArr[end + 1] {
end += 1
}
let tmp = end
// 从中心区域向两侧进行扩散
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)
}
// 开始快进
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]
中心扩散法效率高了很多
因为动态规划方法说到底还是属于暴力解法，所以效率上肯定要比题目特定的优化解法慢，不过动规思路更为通用，此篇也更多为了让自己进一步理解，希望对你也有所帮助。
以下也可以用中心扩散的思想来判定回文：
125. 验证回文串
