[

    ["aa","b"],

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

  ]

题意：切割字符串，使每一个子串都是回文

思路：dfs

选择一个切割点时，假设从起点到切割点的子串是回文，那么该切割点是合法的。能够选择

按这个规则dfs枚举就能够了

复杂度：时间O(n)。空间O(log n)

vector<vector<string> >res;

bool is_palindrome(const string &s, int start, int end){

	while(start < end){

		if(s[start] != s[end - 1]) return false;

		++start; --end;

	}

	return true;

}

void dfs(const string &s, int cur, vector<string>& partitions){

	int size = s.size();

	if(cur == size){

		res.push_back(partitions);

	}

	for(int end = cur + 1; end <= size; ++end){

		if(is_palindrome(s, cur, end)){

			partitions.push_back(s.substr(cur, end - cur));

			dfs(s, end, partitions);

			partitions.pop_back();

		}

	}

}

vector<vector<string>> partition(string s) {

	vector<string> tem;

	dfs(s, 0, tem);

	return res;

}