原題鏈接在這里：https://leetcode.com/problems/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.

題解：

與Word Break相似.?DP問題, 求的是至少切幾刀能全是palindrome. 需要保留的歷史信息是到當(dāng)前點 最少 能分成幾塊palindrome, 用array保存.

更新時如果[i,j]段是palindrome, 到j(luò)點結(jié)束那段就可以從 到i點結(jié)束那段+1 來跟新最小值.

初始化至少每個字母都分開肯定都是palindrome了.

答案dp[len]-1. 最少分成的塊數(shù) 比切的刀數(shù) 多一.

用二維array來村[i, j]段是否是palindrome. 兩邊閉區(qū)間，包括i,j對應(yīng)的char.

Time Complexity: O(len^2). Space: O(len^2).

AC Java:

1 public class Solution { 2 public int minCut(String s) { 3 if(s == null || s.length() == 0){ 4 return 0; 5 } 6 int len = s.length(); 7 boolean[][] isDic = helper(s); 8 int [] res = new int[len+1]; 9 res[0] = 0; 10 for(int i = 0; i < len; i++){ 11 res[i+1] = i+1; 12 for(int j = 0; j <= i; j++){ //error 13 if(isDic[j][i]){ 14 res[i+1] = Math.min(res[i+1],res[j]+1); 15 } 16 } 17 } 18 return res[len] - 1; 19 } 20 21 //helper function builds dictionary 22 private boolean[][] helper(String s){ 23 int len = s.length(); 24 boolean[][] dict = new boolean[len][len]; 25 for(int i = len-1; i>=0; i--){ 26 for(int j = i; j < len; j++){ 27 if(s.charAt(i) == s.charAt(j) && ((j-i)<2 || dict[i+1][j-1] )){ //error 28 dict[i][j] = true; 29 } 30 } 31 } 32 return dict; 33 } 34 }

可以省略掉dic. 對每一個點按照奇數(shù)和偶數(shù)兩種方式 左右延展若是palindrome就更新dp array. 若不是就停止.

Time Complexity: O(len^2). Space: O(len).

AC Java:?

1 class Solution { 2 public int minCut(String s) { 3 if(s == null || s.length() == 0){ 4 return 0; 5 } 6 7 int len = s.length(); 8 int [] dp = new int[len+1]; 9 for(int i = 0; i<=len; i++){ 10 dp[i] = i-1; 11 } 12 for(int i = 0; i<len; i++){ 13 // odd length palindrome 14 for(int l = i, r = i; l>=0 && r<len && s.charAt(l)==s.charAt(r); l--, r++){ 15 dp[r+1] = Math.min(dp[r+1], dp[l]+1); 16 } 17 18 // even length palindrome 19 for(int l = i, r = i+1; l>=0 && r<len && s.charAt(l)==s.charAt(r); l--, r++){ 20 dp[r+1] = Math.min(dp[r+1], dp[l]+1); 21 } 22 } 23 return dp[len]; 24 } 25 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Dylan-Java-NYC/p/4824961.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode Palindrome Partitioning II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。