Dp+dfs solution


  • 0
    S
    class Solution {
    public:
        void dfs(vector<vector<string> > &res, vector<string> &partition, string s, bool **p, int i){
            if(i==s.size()){
                res.push_back(partition);
                return;
            }
            for(int j=i; j<s.size(); j++){
                if(p[i][j]){
                    partition.push_back(s.substr(i, j-i+1));
                    dfs(res, partition, s, p, j+1);
                    partition.erase(partition.begin()+partition.size()-1);
                }
            }
        }
        vector<vector<string>> partition(string s) {
            int n=s.size();
            bool **p=new bool *[n];
            for(int i=0; i<n; i++){
                p[i]=new bool [n];
                p[i][i]=true;
            }
            for(int j=0; j<n; j++){
                for(int i=j; i>=0; i--){
                    if(s[i]==s[j]){
                        if(i+1>=j) p[i][j]=true;
                        else p[i][j]=p[i+1][j-1];
                    }
                    else p[i][j]=false;
                }
            }
            vector<vector<string> > res;
            vector<string> partition;
            dfs(res, partition, s, p, 0);
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.