分割回文串

题目链接：分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

方法一：DFS+逗号分割

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    bool is_hw(string s,int start,int end) {
        while (start < end) {
            if (s[start++] != s[end--]) return false;
        }
        return true;
    }
    void dfs(string s,int start,int i) {
        if (i == s.size()) {
            ans.push_back(path);
            return ;
        }
        if (i < s.size() - 1) {
            dfs(s,start,i+1);
        }
        if (is_hw(s,start,i)) {
            path.push_back(s.substr(start,i-start+1));
            dfs(s,i+1,i+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s,0,0);
        return ans;
    }
};

方法二：DFS+遍历

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    bool is_hw(string s,int start,int end) {
        while (start < end) {
            if (s[start++] != s[end--]) return false;
        }
        return true;
    }
    void dfs(string s,int i) {
        if (i == s.size()) {
            ans.push_back(path);
            return ;
        }
        for (int j = i;j < s.size();j++) {
            if (!is_hw(s,i,j)) continue;
            path.push_back(s.substr(i,j-i+1));
            dfs(s,j+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return ans;
    }
};

方法三：DP+DFS

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<bool>> isPal;
    void buildPal(string s) {
        isPal.assign(s.size(),vector<bool>(s.size(),false));
        for (int i = s.size() - 1;i >= 0;i--) {
            for (int j = i;j < s.size();j++) {
                if (s[i] == s[j] && (j-i <= 2 || isPal[i+1][j-1])) {
                    isPal[i][j] = true;
                }
            }
        }
    }
    void dfs(string s,int i) {
        if (i == s.size()) {
            ans.push_back(path);
            return ;
        }
        for (int j = i;j < s.size();j++) {
            if (!isPal[i][j]) continue;
            path.push_back(s.substr(i,j-i+1));
            dfs(s,j+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        buildPal(s);
        dfs(s,0);
        return ans;
    }
};