題目網址：https://leetcode.cn/problems/palindrome-partitioning/

題意：給一 string s, 將 s 切割成一些 substring, 使每個 substring 皆回文, 返回 s 所有可能的切割方法。

其中, s 僅由小寫英文字母所組成。

Solution：

想法：利用 DFS, 如果切下去是回文, 則遞迴剩下的 substring

class Solution {
public:
    vector<vector<string>> partition(string s) {
        dfs(s, 0, s.size());
        return res;
    }

private:
    vector<string> cur;
    vector<vector<string>> res;

    void dfs(const string& s, const int i, const int n){
        if (i == n) {
            res.emplace_back(cur);
            return;
        }

        for (int j = i; j < n; ++j) {
            if (isPalindrome(s, i, j)) {
                cur.emplace_back(s.substr(i, j - i + 1));
                dfs(s, j + 1, n);
                cur.pop_back();
            }
        }
    }

    bool isPalindrome(const string& s, int left, int right){
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }
};
  • time：$O(n \cdot 2^n)$ ➔ 最壞情況下, s 為 n 個相同的 char
    • 總共 $2^{n-1}$ 種切法（每個 char 之間的間隙都有切 or 不切兩種選擇）
    • 每種耗時 $O(n)$, 判斷每個 substring 是否為回文
  • space：$O(n)$ ➔ 取決於遞迴深度, 最大遞迴深度為 n