leetcode131. 分割回文串

分析

dfs+dp

1. 先用dp算出s[i]-s[j]是否是回文串：f[i][j]表示s[i]-s[j]是否是回文串，转移方程:f[i][j]=f[i+1][j-1]&&s[i]==s[j]
2. 然后用dfs搜索每个回文串的组合。

class Solution {
public:
    vector<vector<int>>f;
    vector<vector<string>> ans;
    vector<string>path;
    void dfs(const string &s,int u){
        if(u==s.size()){
            ans.push_back(path);
            return;
        }
        for(int i=u;i<s.size();i++){
           if(f[u][i]){
               path.push_back(s.substr(u,i-u+1));
               dfs(s,i+1);
               path.pop_back();
           }
        }
    }
    vector<vector<string>> partition(string s) {
        int n=s.size();
        f.assign(n,vector<int>(n,true));//初始均是回文串
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                f[i][j]=f[i+1][j-1]&&(s[i]==s[j]);
            }
        }
        dfs(s,0);
        return ans;
    }
};