Two c++ solutions


  • 0
    Z

    the first one is inspired by Word Break II,56ms,no extra function

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            if(mp.count(s))return mp[s];
            vector<vector<string>> res;
            if(s.size()==0)res.push_back(vector<string>());
            else{
                for(int i=s.size()-1;i>=0;i--){
                int lo=i,hi=s.size()-1;
                while(lo<hi){
                    if(s[lo]!=s[hi])break;
                    lo++,hi--;
                }             
                if(lo>=hi){
                        vector<vector<string>> pre=partition(s.substr(0,i));
                        for(auto&k:pre){
                            k.push_back(s.substr(i));
                            res.push_back(k);
                        }
                    }
                }   
            }
            mp[s]=res;
            return res;
        }
    private:
        unordered_map<string,vector<vector<string>>> mp; 
    };    
    

    the second one is faster and the first thought that hit my mind,a general dfs solution.

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<vector<string>> res;
            vector<string> tmp;
            partition(res,tmp,s);
            return res;
        }
        void partition(vector<vector<string>>& res,vector<string>& tmp,string s){
            if(!s.size())
                if(tmp.size())res.push_back(tmp);
            for(int i=0;i<s.size();i++){
                int lo=0,hi=i;
                while(lo<hi){
                    if(s[lo]!=s[hi])break;
                    lo++,hi--;
                }
                if(lo>=hi){
                    tmp.push_back(s.substr(0,i+1));
                    partition(res,tmp,s.substr(i+1));
                    tmp.pop_back();
                }
            }
        }
    };    
    

Log in to reply
 

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