A recursive solution with memory search


  • -1
    L

    Algo: dfs + memory search

      class Solution {
        public:
            vector<vector<string>> partition(const string & s) {
        		return doPartition(s);
        	}
        
        private:
            vector<vector<string>> & doPartition(const string & s) {
        		auto it = mem.find(s);
        		if (it != mem.end())
        			return it->second;
        
        		vector< vector<string> > ans;
        		for (int i = 1; i <= s.length(); ++i) if (isPalindrome(s.substr(0, i))){
        			const auto & v = partition(s.substr(i));
        			if (v.empty()) {
        				ans.push_back(vector<string> (1, s.substr(0, i)));
        			} else {
        				for (const auto & rest : v) {
        					vector<string> cur;
        					cur.push_back(s.substr(0, i));
        					cur.insert(cur.end(), rest.begin(), rest.end());
        					ans.push_back(cur);
        				}
        			}
        		}
        		return mem[s] = move(ans);
        	}
        
        	bool isPalindrome(const string & s) const {
        		return s == string(s.rbegin(), s.rend());
        	}
        	
        private:
        	unordered_map<string, vector<vector<string> > > mem;
        };

Log in to reply
 

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