Description
給定一個字串
s，找出其中最長的回文子字串。
Example:
Input: s = “babad” Output: “bab”
Intuition#
從每個字元（或每對相鄰字元）向兩邊擴展，找出以該位置為中心的最長回文。
- 回文有奇數長度（單中心）和偶數長度（雙中心）兩種
- 暴力枚舉所有子字串是
O(n^3)，中心擴展法降到O(n^2) - DP 也可以做，但中心擴展更直觀且常數更小
Approaches#
1: Dynamic Programming#
- 概念:
dp[i][j]表示s[i..j]是否為回文，從短子字串填到長子字串 - 時間複雜度:
O(n^2) - 空間複雜度:
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)
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)
}
}補充：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: 中心擴展 — 回文的對稱性質讓我們可以從中心向外檢查
- 關鍵技巧: 記得處理奇偶兩種長度的回文；空間上中心擴展優於 DP 表