LeetCode [132] Palindrome Partitioning II

 132. Palindrome Partitioning II

Hard

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.

 

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lower-case English letters only.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

//C++: method2 56ms time O(n^2) space O(n^2) class Solution { public: int minCut(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, -1));//dp[i][j] is the min cuts of s[i..j];-1 means s[i..j] is not palindrome for(int i=n-1; i>=0; --i){ for(int j=i; j<n; ++j){ if(i==j||(s[i]==s[j]&&(i+1>j-1||dp[i+1][j-1]>=0))){//s[i..j] is palindrome dp[i][j] = 0; if(j<n-1){ if(dp[i][n-1]<0){ dp[i][n-1] = 1+dp[j+1][n-1]; }else{ dp[i][n-1] = min(dp[i][n-1], 1+dp[j+1][n-1]); } } } } } return dp[0][n-1]; } }; class Solution { public: int minCut(string s) { int n = s.size(); int dp[n+1]; for(int i=0; i<=n; ++i){ dp[i] = i-1; } for(int i=0; i<n; ++i){ //odd for(int d=0; i-d>=0 && i+d<n && s[i-d]==s[i+d]; ++d){ dp[i+d+1] = min(dp[i+d+1], 1+dp[i-d]); } //even for(int d=0; i-d>=0 && i+d+1<n && s[i-d]==s[i+d+1]; ++d){ dp[i+d+2] = min(dp[i+d+2], 1+dp[i-d]); } } return dp[n]; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public int minCut(String s) { int n = s.length(); int[][] dp = new int[n][n]; for(int i=0; i<n; ++i) Arrays.fill(dp[i], -1); for(int i=n-1; i>=0; --i){ dp[i][n-1] = n-1-i; for(int j=i; j<n; ++j){ if(i==j) dp[i][j] = 0; else if(i+1==j){ if(s.charAt(i)==s.charAt(j)) dp[i][j] = 0; else dp[i][j] = 1; }else if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]==0){//[i..j] is palindrome dp[i][j] = 0; } if(j+1<n && dp[i][j]==0) dp[i][n-1] = Math.min(dp[i][n-1], 1+dp[j+1][n-1]); } } return dp[0][n-1]; } }