Difficulty: 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
2
3
| Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
|
Solution
Language: Java
20%解法
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
| class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0 || isPalindrome(s, 0, s.length() - 1)) {
return 0;
}
int[] dp = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
int min = Integer.MAX_VALUE;
if (isPalindrome(s, 0, i)) {
min = 0;
} else {
for (int j = 1; j <= i; j++) {
if (isPalindrome(s, j, i)) {
min = Math.min(min, dp[j - 1] + 1);
}
}
}
dp[i] = min;
}
return dp[s.length() - 1];
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
|
85%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
boolean[][] pal = new boolean[n][n];
int[] dp = new int[n];
for (int i = 0; i < s.length(); i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j <= i; j++) {
if (s.charAt(j) == s.charAt(i) && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true;
min = j == 0 ? 0 : Math.min(min, dp[j - 1] + 1);
}
}
dp[i] = min;
}
return dp[n - 1];
}
}
|