Accepted 12ms c++ solution use backtracking.


  • 1
    class Solution {
    public:
        std::vector<std::vector<std::string> > partition(std::string s) {
    		len = s.size();
            std::vector<std::vector<std::string> > res;
    		std::vector<std::string> pars;
    		partitionHelper(s, res, pars, 0);
    		return res;
        }
    private:
    	int len;
        void partitionHelper(std::string &s, std::vector<std::vector<std::string> > &res, std::vector<std::string> &pars, int begin) {
    		if (begin == len)
    			res.push_back(pars);
    		for (int end = begin; end != len; ++end)
    			if (isPalindrome(s, begin, end)) {
    				pars.push_back(s.substr(begin, end - begin + 1));
    				partitionHelper(s, res, pars, end + 1);
    				pars.pop_back();
    			}
        }
    	bool isPalindrome(std::string &s, int begin, int end) {
    		while (begin <= end)
    			if (s[begin++] != s[end--])
    				return false;
    		return true;
    	}	
    };

Log in to reply
 

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