給定一個字串
s，將 s 分割成若干子字串，使得每個子字串都是回文。回傳所有可能的分割方式。
Example:
Input: s = “aab” Output: [[“a”,“a”,“b”],[“aa”,“b”]]
Intuition
TIP
核心思路：回溯嘗試所有分割位置，只有當前子字串是回文時才繼續遞迴。
- 從 index 0 開始，嘗試所有可能的第一段切割（長度 1, 2, 3, …）
- 只有當切下的子字串是回文時，才遞迴處理剩餘部分
- 當 index 到達字串尾部，就得到一組合法分割
Approaches
1. Backtracking + Palindrome Check Each Step — O(n * 2^n) / O(n)
- Idea: 遞迴嘗試每個切割點，用雙指標檢查子字串是否為回文
- Time:
O(n * 2^n)- 最壞 2^n 種切割，每次檢查回文 O(n) - Space:
O(n)- 遞迴深度
class Solution {
fun partition(s: String): List<List<String>> {
val result = mutableListOf<List<String>>()
val current = mutableListOf<String>()
fun isPalindrome(left: Int, right: Int): Boolean {
var l = left; var r = right
while (l < r) {
if (s[l] != s[r]) return false
l++; r--
}
return true
}
fun backtrack(start: Int) {
if (start == s.length) {
result.add(ArrayList(current))
return
}
for (end in start until s.length) {
if (isPalindrome(start, end)) {
current.add(s.substring(start, end + 1))
backtrack(end + 1)
current.removeAt(current.lastIndex)
}
}
}
backtrack(0)
return result
}
}⭐ 2. Backtracking + DP Palindrome Table — O(n^2 + 2^n) / O(n^2)
- Idea: 先用 DP 建立回文判斷表
dp[i][j]，回溯時 O(1) 查詢子字串是否為回文 - Time:
O(n^2 + 2^n)- 預處理 O(n^2)，回溯最壞 O(2^n) - Space:
O(n^2)- 回文表
class Solution {
fun partition(s: String): List<List<String>> {
val n = s.length
val isPalin = Array(n) { BooleanArray(n) }
// DP 預處理：isPalin[i][j] 表示 s[i..j] 是否為回文
for (right in 0 until n) {
for (left in 0..right) {
if (s[left] == s[right] && (right - left <= 2 || isPalin[left + 1][right - 1])) {
isPalin[left][right] = true
}
}
}
val result = mutableListOf<List<String>>()
val current = mutableListOf<String>()
fun backtrack(start: Int) {
if (start == n) {
result.add(ArrayList(current))
return
}
for (end in start until n) {
if (isPalin[start][end]) {
current.add(s.substring(start, end + 1))
backtrack(end + 1)
current.removeAt(current.lastIndex)
}
}
}
backtrack(0)
return result
}
}🔑 Takeaways
- Pattern: 分割問題 = 回溯 + 條件篩選（只在滿足條件時才遞迴）
- Key trick: DP 預處理可以將重複的回文判斷從 O(n) 降到 O(1)；這種「預處理 + 回溯」的組合在很多題目中都有用