🔗 🟡 131. Palindrome Partitioning

tags: `回溯(Backtracking)` `動態規劃(Dynamic Programming)`

題意

給定一個字串 $s$ ，將 $s$ 分割成一些子字串，使得每個子字串都是 回文子字串。

返回 $s$ 的所有可能回文分割方式。

思路：回溯(Backtracking) + 動態規劃(Dynamic Programming)

由於要求出所有可能的分割，因此可以使用回溯法枚舉所有可能的分割。令遞迴函數 $dfs(i)$ 表示以 $s[i]$ 作為目前的起點，則可以枚舉所有可能的終點 $j$ ，若 $s[i:j+1]$ 是回文子字串，則將其加入到 $path$ 中，並繼續遞迴下去，若 $i == n$ ，則表示已經考慮完所有的字元，將 $path$ 加入到答案中。

但這裡有一個問題，如何判斷 $s[i:j+1]$ 是否是回文子字串？可以使用動態規劃的方式預處理出所有子字串是否為回文，令 $is\_palindrome[i][j]$ 表示 $s[i:j+1]$ 是否是回文子字串，則有以下轉移方程：

若 $s[i] == s[j]$ ，則當長度為 $2$ 或 $s[i+1:j]$ 也是回文子字串時， $s[i:j+1]$ 就是回文子字串。

可以先處理長度為 $1$ 的子字串，其皆為回文子字串，再枚舉長度 $2$ 到 $n$ 的子字串。若可能的起點為 $i$ ，則對應的終點 $j$ 為 $i + k - 1$ ，其中 $k$ 為子字串的長度。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot 2^n)$ ，其中 $n$ 為字串 $s$ 的長度，最壞情況下有 $2^n$ 種分割方式(路徑)，而將每條路徑添加到答案中的時間複雜度為 $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n^2)$ ，不考慮答案所需的空間，需要 $\mathcal{O}(n^2)$ 的空間來存儲所有子字串是否為回文，遞迴的深度最多為 $n$ 。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # 動態規劃，預處理出所有子字串是否為回文
        is_palindrome = [[False] * n for _ in range(n)] # is_palindrome[i][j] is True if s[i:j+1] is palindrome
        for i in range(n):
            is_palindrome[i][i] = True
        for k in range(2, n + 1): # 枚舉長度
            for i in range(n - k + 1): # 枚舉起點
                j = i + k - 1 # 對應的終點
                if s[i] == s[j]: # 頭尾相同，若 長度為2 或 內部也是回文(從 is_palindrome[i+1][j-1] 轉移) ，則是回文
                    if k == 2 or is_palindrome[i + 1][j - 1]:
                        is_palindrome[i][j] = True
        # 回溯，枚舉所有可能的分割
        ans = []
        path = []
        def dfs(i: int) -> None: # backtracking
            if i == n:
                ans.append(path[:]) # copy path
                return
            for j in range(i, n): # 枚舉終點
                if is_palindrome[i][j]:
                    path.append(s[i:j+1])
                    dfs(j + 1) # 
                    path.pop()
        dfs(0) # 起點從0開始
        return ans

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // 動態規劃，預處理出所有子字串是否為回文
        vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) is_palindrome[i][i] = true; // 長度 1
        for (int k = 2; k <= n; k++) { // 枚舉長度 k
            for (int i = 0; i < n - k + 1; i++) { // 枚舉起點 i
                int j = i + k - 1; // 對應的終點 j
                if (s[i] == s[j] && (k == 2 || is_palindrome[i + 1][j - 1])) { // 頭尾相同，若 長度為2 或 內部也是回文(從 is_palindrome[i+1][j-1] 轉移) ，則是回文
                    is_palindrome[i][j] = true;
                }
            }
        }
        // 回溯，枚舉所有可能的分割
        vector<vector<string>> ans;
        vector<string> path;
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.push_back(path);
                return;
            }
            for (int j = i; j < n; j++) { // 枚舉終點 j
                if (is_palindrome[i][j]) {
                    path.push_back(s.substr(i, j - i + 1));
                    dfs(j + 1);
                    path.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};