LeetCode Palindrome Partitioning II

LeetCode Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


动态规划题目,类似于矩阵链相乘。设dp[i][j]表示s[i,...,j]是否为回文串,cut[j]表示s[1,...,j]需要多少刀才能切成回文串。动态规划运行到最后返回cut[n]。

对于cut[j],切第一刀的时候,我们尝试前面j个切割位点,比如我们尝试切第i点,则s[1,...,j]被分成了s[1,...,i-1]和s[i,...,j],如果s[i,...,j]为回文串,则s[i,...,j]不需要再切了,又因为cut[i-1]我们之前已经算过了,所以在i处切一刀,有cut[j]=cut[i-1]+1。尝试所有的切割位点i,找最小的cut[j]。

如果发现i=1的时候s[i,...,j]为回文串,则s[1,...,j]不需要再切了,所以cut[j]=0。

完整代码如下:

class Solution {
public:
	int minCut(string s) {
		int n = s.size();
		vector<vector<bool>> dp(n, vector<bool>(n, false));
		for (int i = 0; i < n; i++)
			dp[i][i] = true;
		vector<int> cut(n, 0); // # of cut for s[0,j]
		for (int j = 0; j < n; j++)
		{
			cut[j] = j; // set maximum # of cut
			for (int i = 0; i <= j; i++)
			{
				if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]))
				{
					dp[i][j] = true;
					
					if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
						cut[j] = min(cut[j], cut[i - 1] + 1);
					else // if [0...j] is palindrome, no need to cut    
						cut[j] = 0;
				}
			}

		}
		return cut[n - 1];
	}
};

本代码提交AC,用时84MS。

二刷。参考讨论区一个大神的做法:https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space。这种方法不需要上面的做法的dp数组,效率也会高很多。

还是需要cuts数组,cuts[i]表示前i个字符切成回文子串,最少的刀数。对于每一个字符,我们枚举以该字符为中心,能够扩展到的最长的回文子串的长度,比如下图,以b为中心扩展,扩展到aba是一个回文子串,那么要把Y切成回文子串,需要的刀数不超过把X切成回文子串需要的刀数加1,也就是cuts[Y]=min(cuts[Y],cuts[X]+1)。

注意,扩展的时候,需要考虑到以b为中心的回文子串的长度是奇数还是偶数。

.......aba...
|<-X->| ^
|<---Y-->|

通过枚举每一个回文中心点,我们可以算到所有的cuts,最后返回cuts[n]。完整代码如下:

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串,最少的刀数
        for(int i = 0; i <= n; ++i) cuts[i]  = i - 1;
        
        for(int i = 0; i < n; ++i) {
            for(int j = 0; i - j >= 0 && i + j < n && s[i - j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1);
            
            for(int j = 1; i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j + 1] + 1);
        }
        return cuts[n];
    }
};

本代码提交AC,用时6MS,神速。

Leave a Reply

Your email address will not be published. Required fields are marked *