Palindrome Partitioning II (LeetCode)

题目：

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.

思路：

Palindrome Partitioning需要收集所有回文切分的解，而这一题只需要求最少的切分次数，如果直接由原来的算法，然后搜索最小切分次数的解，复杂度是 $$O(N^3)$$ ，提交后TLE。

这里需要利用两次DP：

1）首先定义一个二维数组flag[N][N]，其中flag[i][j]表示子字符串s[i:j+1]是否是回文，显然若i==j，即长度为1的字符串，则f[i][i]=True，若i+1==j，则需要再查看s[i]和s[i+1]是否相等，如果相等则为True，若j-i>=2，同样先看s[i]和s[j]，如果相等，则返回flag[i+1][j-1]，否则直接设置为False；

2）再定义一个记录最小切分次数的一维数组count，其中count[i]表示子字符串s[:i+1]的最小切分次数，如果flag[0][i]==True，则为0，否则需要寻找最小的切分方式j，使得count[j]+1最小，且s[j+1:i+1]是回文。

不过可惜，思路虽然没错，但是Python实现依旧TLE，本地跑了一下超时的数据，大概0.807s左右，后来陈大哥用C++实现，AC......

网上看到一个更加简短的Python代码，非常赞，不过同样TLE，一起Po上来吧，三份代码如下，其中C++版本由同实验室陈大哥提供，Python版后面有几个测试数据。。。

bool f[0x1010][0x1010];
class Solution {
private:
    int g[0x1010];
    string str;

public:
    int minCut(string s) {
        str = s;
        int n = str.length();

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                f[i][j] = true;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (str[j] == str[j + i]) f[j][j + i] = f[j + 1][j + i - 1];
                else f[j][j + i] = false;
            }
        }

        g[0] = 0;
        for (int i = 1; i < n; ++i) {
            if (f[0][i]) g[i] = 0;
            else {
                g[i] = 0x1010;
                for (int j = 0; j < i; ++j) {
                    if (f[j + 1][i]) g[i] = min(g[i], g[j] + 1);
                }
            }
        }
        return g[n - 1];
    }
};

import time

class Solution:
	# @param s, a string
	# @return a list of lists of string
	def minCut(self, s):
		N = len(s)
		dp = [N-j for j in range(N+1)]
		p = [[False for i in range(N)] for j in range(N)]
		for i in xrange(N-1,-1,-1):
			for j in xrange(i, N):
				if s[i] == s[j] and (((j - i) < 2) or p[i+1][j-1]):
					p[i][j] = True
					dp[i] = min(1+dp[j+1], dp[i])
		return dp[0]-1
	
	def minCut2(self, s):
		N = len(s)
		if N<=1:
			return [[s]]
		count = [-1 for j in range(N)]
		flag = [[False for j in range(N)] for i in range(N)]
		for i in xrange(N):
			flag[i][i] = True
			if i+1<N and s[i]==s[i+1]:
				flag[i][i+1] = True
		for i in xrange(2,N):
			for j in xrange(N-i):
				if s[j]==s[j+i] and flag[j+1][j+i-1]:
					flag[j][j+i] = True
		
		count[0] = 0
		for i in xrange(1,N):
			if flag[0][i]:
				count[i] = 0
			else:
				count[i] = i
				for j in xrange(i):
					if flag[j+1][i]:
						count[i] = min(count[i],count[j]+1)
		return count[N-1]

s = Solution()
print s.minCut2('aab')
print s.minCut2("fifgbeajcacehiicccfecbfhhgfiiecdcjjffbghdidbhbdbfbfjccgbbdcjheccfbhafehieabbdfeigbiaggchaeghaijfbjhi")
print s.minCut2("apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp")
t1 = time.time()
print s.minCut2("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
t2 = time.time()
print 'finished in %f seconds' % (t2-t1)

nicklhy