給定一個字串
s，找出其中最長的回文子字串。
Example:
Input: s = “babad” Output: “bab”
Intuition
TIP
從每個字元（或每對相鄰字元）向兩邊擴展，找出以該位置為中心的最長回文。
- 回文有奇數長度（單中心）和偶數長度（雙中心）兩種
- 暴力枚舉所有子字串是
O(n^3)，中心擴展法降到O(n^2) - DP 也可以做，但中心擴展更直觀且常數更小
Approaches
1. Dynamic Programming — O(n^2) / O(n^2)
- Idea:
dp[i][j]表示s[i..j]是否為回文，從短子字串填到長子字串 - Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun longestPalindrome(s: String): String {
val n = s.length
val dp = Array(n) { BooleanArray(n) }
var start = 0
var maxLen = 1
for (i in 0 until n) dp[i][i] = true
for (len in 2..n) {
for (i in 0..n - len) {
val j = i + len - 1
dp[i][j] = s[i] == s[j] && (len == 2 || dp[i + 1][j - 1])
if (dp[i][j] && len > maxLen) {
start = i
maxLen = len
}
}
}
return s.substring(start, start + maxLen)
}
}⭐ 2. Expand Around Center — O(n^2) / O(1)
- Idea: 對每個位置嘗試奇數和偶數兩種中心擴展，記錄最長結果
- Time:
O(n^2) - Space:
O(1)
class Solution {
fun longestPalindrome(s: String): String {
var start = 0
var maxLen = 0
fun expand(l: Int, r: Int) {
var left = l; var right = r
while (left >= 0 && right < s.length && s[left] == s[right]) {
left--; right++
}
val len = right - left - 1
if (len > maxLen) {
start = left + 1
maxLen = len
}
}
for (i in s.indices) {
expand(i, i) // 奇數長度
expand(i, i + 1) // 偶數長度
}
return s.substring(start, start + maxLen)
}
}Note: Manacher's Algorithm O(n)
Manacher 演算法可以在 O(n) 時間內找到最長回文子字串，但面試中很少要求。
class Solution {
fun longestPalindrome(s: String): String {
// 插入分隔符: "abc" -> "^#a#b#c#$"
val t = StringBuilder("^")
for (c in s) t.append("#$c")
t.append("#$")
val n = t.length
val p = IntArray(n)
var center = 0; var right = 0
for (i in 1 until n - 1) {
if (i < right) p[i] = minOf(right - i, p[2 * center - i])
while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++
if (i + p[i] > right) { center = i; right = i + p[i] }
}
val maxIdx = p.indices.maxByOrNull { p[it] }!!
val maxLen = p[maxIdx]
val start = (maxIdx - maxLen) / 2
return s.substring(start, start + maxLen)
}
}🔑 Takeaways
- Pattern: 中心擴展 — 回文的對稱性質讓我們可以從中心向外檢查
- Key trick: 記得處理奇偶兩種長度的回文；空間上中心擴展優於 DP 表