[LeetCode]Palindrome Partition

Backtrack的题型。相对于每次递归用O(n)的时间来判断当前substring是否为palindrome，我们可以对string做预处理，生产一个map来表示substr(i, j)是否是palindrome，这样的话O(1)时间即可判断。空间复杂度O(n^2)，因为要存bool来表示任意substring是否为palindrome。时间复杂度worst caseO(2^(n - 1))，因为最坏情况在每一处我们都要考虑切割与不切割的情况，比如，"aaaa.....aa"，但是一般情况而言，我们的剪枝会有效的减小时间复杂度，代码如下：

	class Solution {
	public:
	vector<vector<string>> partition(string s) {
	int len = s.size();
	vector<vector<bool>> isPalin(len, vector<bool>(len, false));
	for(int i = 0; i < len; ++i)
	{
	for(int j = 0; j <= i; ++j)
	{
	if(s[i] == s[j] && (i - j < 2 || isPalin[j + 1][i - 1]))
	isPalin[j][i] = true;
	}
	}
	vector<vector<string>> res;
	vector<string> curr;
	backtrack(res, curr, isPalin, s, 0);
	return res;
	}
	private:
	void backtrack(vector<vector<string>>& res, vector<string>& curr, const vector<vector<bool>>& isPalin, const string s, int start)
	{
	if(start >= s.size())
	{
	res.push_back(curr);
	return;
	}
	for(int i = start; i < s.size(); ++i)
	{
	if(isPalin[start][i])
	{
	curr.push_back(s.substr(start, i - start + 1));
	backtrack(res, curr, isPalin, s, i + 1);
	curr.pop_back();
	}
	}
	}
	};

view raw Palindrome Partitioning.cpp hosted with ❤ by GitHub