/*
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"] */
#include<vector>
#include<string>
using namespace std;
#if 0//wrong
class Solution {
public:
	vector<vector<string>> partition(string s) {
		int len = s.size();
		vector<vector<string>> res;
		auto s_iter = s.begin();
		for (int i = 0; i < len; i++){
			vector<string> tmp;
			for (int j = i; j < len; j++){
				//string s(s_iter + i, s_iter + j + 1);
				string str = s.substr(i, j + 1);
				if (is_palindrome(s, i,j)){
					tmp.push_back(s);
				}
			}
			res.push_back(tmp);
		}
		return res;
	}
private:
	bool is_palindrome(string &s, int head_index, int tail_index){

		while (head_index < tail_index){
			if (s[head_index]!= s[tail_index])
				return false;
			head_index++;
			tail_index--;
		}
		return true;
	}
};
#elif 1
//LeetCode, Palindrome Partitioning
// 时间复杂度 O(2^n)，空间复杂度 O(n)
class Solution {
public:
	vector<vector<string>> partition(string s) {
		vector<vector<string>> result;
		vector<string> output; // 一个 partition 方案
		DFS(s, 0, output, result);
		return result;
	}
	// 搜索必须以 s[start] 开头的 partition 方案
	void DFS(string &s, int start, vector<string>& output,
		vector<vector<string>> &result) {
		if (start == s.size()) {
			result.push_back(output);
			return;
		}
		for (int i = start; i < s.size(); i++) {
			if (isPalindrome(s, start, i)) { 
				output.push_back(s.substr(start, i - start + 1));
				DFS(s, i + 1, output, result); // 继续往下砍
				output.pop_back(); // 撤销上一个 push_back 的砍
			}
		}
	}
	bool isPalindrome(string &s, int start, int end) {
		while (start < end) {
			if (s[start] != s[end]) return false;
			start++;
			end--;
		}
		return true;
	}
};
#endif
void test0(){
	string s= "aab";
	Solution ss;
	auto res = ss.partition(s);
	int we;
}
int main(){
	test0();
	system("pause");
	return 0;
}

Palindrome Partitioning