LeetCode Q131: Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

	class Solution {
	public:
	bool isPalindrome(string s){
	for(int i=0; i<s.length()/2; i++){
	if(s[i]!=s[s.length()-1-i])
	return false;
	}
	return true;
	}
	void helper(string s, vector<string> curPartitions, vector<vector<string> >& res){
	if(s.length()==0){
	res.push_back(curPartitions);
	return;
	}
	for(int i=0; i<s.length(); i++){
	string tmp=s.substr(0, i+1);
	if(isPalindrome(tmp)){
	vector<string> tmpCurPartition=curPartitions;
	tmpCurPartition.push_back(tmp);
	string ss=s.substr(i+1, s.length()-i-1);
	helper(ss, tmpCurPartition, res);
	}
	}
	}
	vector<vector<string> > partition(string s) {
	vector<string> curPartitions;
	vector<vector<string> >res;
	if(s.length()==0)
	return res;
	helper(s, curPartitions, res);
	return res;
	}
	};

view raw Q131PalindromePartition.cpp hosted with ❤ by GitHub