LeetCode Palindrome Partitioning II

原题链接在这里：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. 需要保留的历史信息是到当前点 最少 能分成几块palindrome, 用array保存.

更新时如果[i,j]段是palindrome, 到j点结束那段就可以从 到i点结束那段+1 来跟新最小值.

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

答案dp[len]-1. 最少分成的块数 比切的刀数 多一.

用二维array来村[i, j]段是否是palindrome. 两边闭区间，包括i,j对应的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. 对每一个点按照奇数和偶数两种方式 左右延展若是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 }

 

转载于:https://www.cnblogs.com/Dylan-Java-NYC/p/4824961.html

总结

以上是生活随笔为你收集整理的LeetCode Palindrome Partitioning II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。