[LeetCode]Palindrome Partitioning II

DP[i]表示s中前i个char的最小cut数。我们可以得到递推方程：

• DP[i] = min(DP[j ] + 1), 如果存在j并且j满足条件s[j, i]为palindrome
• 否则DP[i] = i - 1

我们有两种方法可以实现。因为找string的所有回文一般有两种方法。第一种，我们用另外一个二维数组isPalin[i][j]来表示s[i, j]是否为回文。我们可以在更新DP的时候同时更新isPalin，空间复杂度O(n^2)，时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int minCut(string s) {
	int len = s.size();
	vector<vector<bool>> isPalin(len, vector<bool>(len, false));
	vector<int> cuts(len + 1, -1);
	for(int i = 0; i < len; ++i)
	{
	int minCut = 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;
	minCut = min(minCut, 1 + cuts[j]);
	}
	}
	cuts[i + 1] = minCut;
	}
	return cuts[len];
	}
	};

view raw Palindrome Partitioning II_1.cpp hosted with ❤ by GitHub

第二种，我们可以根据从每个字符开始向两边展开来求所有的回文，检测到回文的时候就更新对应DP的位置。因为我们看到当前substring不是回文就会立刻中断，虽然时间复杂度worst case也是O(n^2)，但整体来讲会稍微快一点，并且不需要额外空间。但因为DP需要空间，所以整体空间复杂度是O(n)，代码如下：

	class Solution {
	public:
	int minCut(string s) {
	int len = s.size();
	vector<int> cuts(len + 1);
	for(int i = 0; i <= len; ++i)
	cuts[i] = i - 1;
	for(int i = 0; i < len; ++i)
	{
	//odd length
	for(int j = 0; i - j >= 0 && i + j < len && s[i - j] == s[i + j]; ++j)
	cuts[i + j + 1] = min(cuts[i + j + 1], 1 + cuts[i - j]);
	//even length
	for(int j = 0; i - j >= 0 && i + j + 1 < len && s[i - j] == s[i + j + 1]; ++j)
	cuts[i + j + 2] = min(cuts[i + j + 2], 1 + cuts[i - j]);
	}
	return cuts[len];
	}
	};

view raw Palindrome Partitioning II_2.cpp hosted with ❤ by GitHub