Palindrome Partitioning

将输入的串进行分割，使得每个部分都是回文串，返回所有满足这样要求的分割。

在word break 系列中，我们在dfs时，继续深层递归的判定条件是当前的子部分在字典中存在，这里将判定条件改为当前的子部分是回文串，其他都是一样。

class Solution {
public:
	bool isPalindrome(int start, int end, string& s){
		while(start<end)
		{
			if(s[start]!=s[end]) return false;
			start++,end--;
		}
		return true;
	}
	void dfs(int cur, string& s, vector<vector<string> >& re, vector<string>& cur_re)
	{
		if(cur == s.size()){
			re.push_back(cur_re);
			return;
		}
		for (int i = cur; i < s.size(); ++i)
		{
			if(isPalindrome(cur, i, s)){
				cur_re.push_back(s.substr(cur, i - cur + 1));
				dfs(i + 1, s, re, cur_re);
				cur_re.pop_back();
			}
		}
	}
	vector<vector<string> > partition(string s) {
        vector<vector<string> > re;
		vector<string> cur_re;
		if(s.size() == 0) return re;
		dfs(0, s, re, cur_re);
		return re;
	}
};

Palindrome Partitioning

原文：http://blog.csdn.net/shiquxinkong/article/details/18709083