12 ms c++ solution using backtracking


  • 0
    L

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

    class Solution {
    public:
    	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)
    					ret.push_back(comb);
    				else
    				    helper(s, i+1, ret, comb);
    				comb.pop_back();
    			}
    		}
    	}
    
        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.