12 ms c++ solution using backtracking

  • 0

    Nothing tricky. But I want to know if there a more effective way to determine if a substring is palindrome.

    class Solution {
    	bool isPalindrome(string& s, int start, int end)
    		while(start < end)
    			if(s[start++] != s[end--])
    				return false;
    		return true;
    	void helper(string& s, int start, 
    		vector<vector<string> >& ret, vector<string>& comb)
    		for(int i = start; i < s.size(); i++)
    			if(isPalindrome(s, start, i))
    				comb.push_back(s.substr(start, i-start+1));
    				if(i == s.size() - 1)
    				    helper(s, i+1, ret, comb);
        vector<vector<string> > partition(string s) {
            vector<vector<string> > ret;
            vector<string> comb;
            helper(s, 0, ret, comb);
            return ret;

Log in to reply

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