Lot lot faster than the fastest solution (DP + Backtracking)


#1
bool ispalin(const string& s){
        for(int i = 0; i<s.size(); i++){
            if(s[i] != s[s.size() - i - 1]) return false;
        }
        return true;
}

vector<vector<string>> solve(const string& a, unordered_map<int, vector<vector<string>> >& map, int start){
    
    if(start == a.size()){
        return {{" "}};
    }
    
    vector<vector<string>> ans;
    
    for(int i = 0; i<a.size(); i++){
        vector<vector<string>> rem;
        vector<string> temp;
        if(ispalin(a.substr(start, i- start +1))){
            temp.push_back(a.substr(start, i- start +1));
            
            if(map.count(i+1)){
                rem = map[i+1];
            }
            else {
                rem = solve(a, map, i+1);
                map.insert({i+1, rem});
            }
        }
        
        if(rem.size() == 1 && rem[0][0] == " "){
            ans.push_back(temp);
        } 
        
        for(auto& p : rem){
            vector<string> h = temp;
            for(auto& k : p){
                h.push_back(k);
            }
            ans.push_back(h);
        }
        
    }
    return map[start] = ans;
}

vector<vector<string> > Solution::partition(string a) {
  
    unordered_map<int, vector<vector<string>> > map;
    return solve(a, map, 0);
}