题目描述

给定一个字符串 ss，将 ss 划分成若干部分，使得每一部分都是回文串。

请返回所有合法的划分方案。

样例

输入："aab"
输出：
[
  ["aa","b"],
  ["a","a","b"]
]

算法

(回溯+剪枝) $O(2^n*n)$

经典回溯题，注意每次回溯调用DFS是，先行判断是否为palindrome

时间复杂度 $O(2^n*n)$

C++ 代码

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;

    bool isPalindrome(const string& s, int start, int end) {
        if (start == end) return true;
        else {
            while (start + 1 < end && s[start] == s[end]) {
                start++;
                end--;
            }
            if (start + 1 >= end && s[start] == s[end]) return true;
            else return false;
        }
    }

    void DFS(const string& s, int u) {
        // termination
        if (u == s.size()) res.emplace_back(path);
        // progress
        else {
            for (int i = u; i < s.size(); i++)
                if (isPalindrome(s, u, i)) {
                    path.emplace_back(s.substr(u, i - u + 1));
                    DFS(s, i + 1);
                    path.pop_back();
                }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        DFS(s, 0);
        return res;
    }
};