Leetcode Palindrome Partitioning II

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.

好困难的一道题目，我评价的难度指数为五星级。（在不看提示，不参考别人程序的前提下思考）

因为我研究了很长时间，没看提示的情况下，观察了各种可能的判断，始终没有找到可行的快捷方法，判断时间效率必定为O(n*n)，没有找到什么规律可以提高效率。最后上网搜索也没看到有可行方法。

整个题目解决，如果是可以O(n*n*n)时间复杂度是稍微简单点的，不然对动态规划法的运用就要求比较高了。

下面程序分两个函数，两步解决问题：

函数1 先产生一个回文表，记录了所有子串是回文的表。

函数2 判断最小分隔步数

	int minCut(string s) 
	{
		if (s.empty()) return 0;

		vector
  
    A(s.length());
		vector
   
     > table = genPalindromeTable(s); if (table[0][s.length()-1]) return 0; for (int i = 1; i < s.length(); i++) { if (table[0][i]) { A[i] = 0; continue; } A[i] = A[i-1]+1; for (int j = 1; j < i; j++) { if (table[j][i]) { A[i] = min(A[i], A[j-1]+1); //if (A[j] == A[j-1]+1) break;//加不加这句都好像不影响效率 } //if (A[i] == 1) break;//加不加这句都好像不影响效率 //genPalindromeTable才是效率瓶颈 } } return A[s.length()-1]; } vector
    
      > genPalindromeTable(string &s) { vector
     
       > table(s.length(), vector
      
       (s.length(), true)); for (int i = 1; i < s.length(); i++) { if (s[i] != s[i-1]) table[i-1][i] = false; } for (int d = 2; d < s.length(); d++) { for (int i = 0, j = d; j < s.length(); i++, j++) { if (table[i+1][j-1] && s[i] == s[j]); else table[i][j] = false; } } return table; }
      
     
    
   
  

虽然这个程序和我上面的程序思想是一样的，还有时间效率也是一样的，我的分开两个函数也许清晰点。

leetcode上总有人能这么简洁的程序，十分佩服。

int minCut(string str){
		int leng = str.size();

		vector
  
    dp(leng+1);
		vector
   
     > palin(leng, vector
    
     (leng)); for(int i = 0; i <= leng; i++) dp[i] = leng-i; for(int i = leng-1; i >= 0; i--){ for(int j = i; j < leng; j++){ if(str[i] == str[j] && (j-i<2 || palin[i+1][j-1])){ palin[i][j] = true; dp[i] = min(dp[i],dp[j+1]+1); } } } return dp[0]-1; }
    
   
  

这需要对本题题目和动态规划法理解的十分透切才能写出来吧。
把我是上面的程序中的两个函数都合并起来了，填写回文表和判断都一步写成，武学中一气呵成啊。呵呵

我还写了个纯粹一个动态规划法的程序，思路是像分块矩阵相乘(matrix chain)这样的题目，不过时间效率是O(n*n*n)，所以leetcode上超时。

//正确程序但是超时
	int minCut(string s) 
	{
		vector
  
    > table(s.length(), vector
   
    (s.length())); for (int d = 2; d <= s.length(); d++) { for (int row = 0; row <= s.length()-d; row++) { int col = row + d - 1; if (table[row+1][col-1] == 0 && s[row] == s[col]) continue; table[row][col] = INT_MAX; for (int i = row; i < col; i++) { table[row][col] = min(table[row][col], table[row][i] + table[i+1][col] + 1); if (table[row][col] == 1) break; } } } return table[0][s.length()-1]; }