131. Palindrome Partitioning

Medium

Description

給定一個字串 s，將 s 分割成若干子字串，使得每個子字串都是回文。回傳所有可能的分割方式。

Example:

Input: s = “aab” Output: [[“a”,“a”,“b”],[“aa”,“b”]]

Intuition#

核心思路：回溯嘗試所有分割位置，只有當前子字串是回文時才繼續遞迴。

從 index 0 開始，嘗試所有可能的第一段切割（長度 1, 2, 3, …）
只有當切下的子字串是回文時，才遞迴處理剩餘部分
當 index 到達字串尾部，就得到一組合法分割

Approaches#

1: Backtracking + 每次檢查回文#

概念: 遞迴嘗試每個切割點，用雙指標檢查子字串是否為回文
時間複雜度: O(n * 2^n) - 最壞 2^n 種切割，每次檢查回文 O(n)
空間複雜度: 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 預處理回文表#

概念: 先用 DP 建立回文判斷表 dp[i][j]，回溯時 O(1) 查詢子字串是否為回文
時間複雜度: O(n^2 + 2^n) - 預處理 O(n^2)，回溯最壞 O(2^n)
空間複雜度: 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: 分割問題 = 回溯 + 條件篩選（只在滿足條件時才遞迴）
關鍵技巧: DP 預處理可以將重複的回文判斷從 O(n) 降到 O(1)；這種「預處理 + 回溯」的組合在很多題目中都有用