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.
|
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 |
public class Solution { public
int minCut(String s) { int
cuts = 0; int
len = s.length(); if(len > 1){ boolean[][] isPalindrome = new
boolean[len][len]; //s.substring(i, i + 1) is palindrome (substring with length 1) for(int
i = 0; i < len; ++i) isPalindrome[i][i] = true; //substring with length > 1 for(int
i = len - 2; i >= 0; --i){ for(int
j = len - 1; j > i; --j){ if(j - i == 1){ isPalindrome[i][j] = (s.charAt(i) == s.charAt(j)); isPalindrome[j][i] = isPalindrome[i][j]; } else{ isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]) ? true
: false; isPalindrome[j][i] = isPalindrome[i][j]; } } } int[] minCutting = new
int[len]; for(int
i = len - 1; i >= 0; --i){ if(isPalindrome[i][len - 1]) minCutting[i] = 0; else{ int
min = len + 1; for(int
j = i + 1 ; j < len; ++j){ if(isPalindrome[i][j - 1]) min = (min < 1
+ minCutting[j])? min : 1
+ minCutting[j]; } minCutting[i] = min; } } cuts = minCutting[0]; } return
cuts; }} |
leetcode--Palindrome Partitioning II
原文：http://www.cnblogs.com/averillzheng/p/3543742.html