116.最长回文子串
题目
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
- 输入：s = "babad"
- 输出："bab"
- 解释："aba" 同样是符合题意的答案。
示例 2：
- 输入：s = "cbbd"
- 输出："bb"
思路
每个回文子串都有一个“中心”。
中心有两种:
- 奇数长度中心：一个字符，比如 aba 的中心是 b
- 偶数长度中心：两个字符中间，比如 abba 的中心是两个 b
所以我们遍历每个位置，把它当成中心，分别扩散两次:
- 以 i 为中心，找奇数长度回文
- 以 i 和 i + 1 为中心，找偶数长度回文
每次扩散时：
- 左边指针往左走
- 右边指针往右走
- 只要两个字符相等，就继续扩
- 不相等就停
class Solution {
fun longestPalindrome(s: String): String {
// 如果字符串长度小于 2，本身就是最长回文
if (s.length < 2) return s
// 记录最长回文子串的起始位置
var start = 0
// 记录最长回文子串的最大长度
var maxLen = 1
// 遍历每个位置，把它当作回文中心
for (i in s.indices) {
// 情况 1：奇数长度回文
// 比如 "aba"，中心是一个字符
val len1 = expandFromCenter(s, i, i)
// 情况 2：偶数长度回文
// 比如 "abba"，中心是两个字符中间
val len2 = expandFromCenter(s, i, i + 1)
// 当前中心能扩出来的最长长度
val len = maxOf(len1, len2)
// 如果当前找到的回文更长，就更新答案
if (len > maxLen) {
maxLen = len
// 根据中心 i 和长度 len，反推出起点
start = i - (len - 1) / 2
}
}
// 截取最长回文子串
return s.substring(start, start + maxLen)
}
private fun expandFromCenter(s: String, leftStart: Int, rightStart: Int): Int {
var left = leftStart
var right = rightStart
// 只要左右没有越界，并且左右字符相等，就继续往外扩
while (left >= 0 && right < s.length && s[left] == s[right]) {
left--
right++
}
// 循环结束时，left 和 right 已经多走了一步
// 所以真正的回文长度是 right - left - 1
return right - left - 1
}
}
复杂度
- 时间复杂度: O(n^2)
- 空间复杂度: O(1)
动态规划思路：用小回文推出大回文
核心想法
一个字符串是回文，需要满足两个条件： 首尾字符相同。 去掉首尾后的子串也是回文。 例如 "aba"：首尾都是 'a'，去掉首尾后是 "b"（是回文），所以 "aba" 是回文。
又如 "abca"：首尾都是 'a'，但去掉首尾后是 "bc"（不是回文），所以 "abca" 不是回文。
所以，我们可以从短的回文开始，逐步推出更长的回文。
状态定义
设 dp[i][j] 表示子串 s[i..j]（从第 i 个字符到第 j 个字符）是不是回文。 dp[i][j] = true 表示是回文 dp[i][j] = false 表示不是回文 状态转移 纯文本 如果 s[i] == s[j] 并且 (j - i <= 2 或 dp[i+1][j-1] == true)： 那么 dp[i][j] = true 否则： dp[i][j] = false 解释： j - i <= 2 表示子串长度 ≤ 3（即长度为1、2或3）。 长度1："a" 一定是回文。 长度2："aa" 首尾相同就是回文。 长度3："aba" 首尾相同且中间只有一个字符，一定是回文。 这些情况不需要看内部的子串。 如果长度 > 3，则需要看去掉首尾后的子串 s[i+1..j-1] 是不是回文。 填表顺序
因为 dp[i][j] 依赖于 dp[i+1][j-1]（左下角），所以我们需要按子串长度从小到大来填表，或者从下往上、从左往右填。
更直观的是按长度枚举：先处理所有长度为1的子串，再处理长度为2的，然后是长度为3的……直到长度为 n。
记录答案
在填表过程中，每当发现 dp[i][j] = true 且当前子串长度大于之前记录的最长长度时，就更新最长回文的起始位置和长度。
手动模拟（以 "babad" 为例）
字符串 s = "b a b a d"，长度 n=5。
初始化一个 5x5 的布尔表，所有值默认为 false。
第一步：所有长度为1的子串都是回文
dp[0][0]=true, dp[1][1]=true, dp[2][2]=true, dp[3][3]=true, dp[4][4]=true
当前最长回文长度=1，起始位置=0。
第二步：长度为2的子串 i=0, j=1: s[0]=='b', s[1]=='a'，不相同 → false i=1, j=2: 'a' vs 'b' → false i=2, j=3: 'b' vs 'a' → false i=3, j=4: 'a' vs 'd' → false 没有长度为2的回文。 第三步：长度为3的子串 i=0, j=2: s[0]=='b', s[2]=='b'，相同，且 j-i=2 ≤ 2 → true。回文 "bab"，长度3，更新最长。 i=1, j=3: 'a' vs 'a'，相同，长度3 → true。回文 "aba"，长度3，同样最长。 i=2, j=4: 'b' vs 'd' → false 第四步：长度为4的子串 i=0, j=3: s[0]=='b', s[3]=='a'，不相同 → false i=1, j=4: 'a' vs 'd' → false 第五步：长度为5的子串 i=0, j=4: s[0]=='b', s[4]=='d' → false 最终最长回文长度为3，起始位置可以是0或1，返回 "bab" 或 "aba"。
class Solution {
fun longestPalindrome(s: String): String {
val n = s.length
if (n < 2) return s // 单个字符或空串直接返回
// dp[i][j] 表示子串 s[i..j] 是否是回文
val dp = Array(n) { BooleanArray(n) }
var start = 0 // 最长回文的起始位置
var maxLen = 1 // 最长回文的长度
// 所有长度为1的子串都是回文
for (i in 0 until n) {
dp[i][i] = true
}
// 按子串长度从小到大枚举
// len 表示子串长度，从2到n
for (len in 2..n) {
// i 是子串的起始位置
for (i in 0..n - len) {
val j = i + len - 1 // 子串的结束位置
if (s[i] == s[j]) {
// 如果子串长度 <= 3，直接判定为回文
// 否则需要看去掉首尾后的子串是否是回文
if (len <= 3 || dp[i + 1][j - 1]) {
dp[i][j] = true
// 更新最长回文
if (len > maxLen) {
maxLen = len
start = i
}
}
}
// 如果 s[i] != s[j]，dp[i][j] 保持 false（默认值）
}
}
// 返回最长回文子串
return s.substring(start, start + maxLen)
}
}
- 邮箱 ：charon.chui@gmail.com
- Good Luck!