-
Notifications
You must be signed in to change notification settings - Fork 11
Expand file tree
/
Copy pathPalindromePartitioningIIPractice.java
More file actions
65 lines (53 loc) · 1.93 KB
/
PalindromePartitioningIIPractice.java
File metadata and controls
65 lines (53 loc) · 1.93 KB
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*PalindromePartitioningIIPractice.java
Palindrome Partitioning II
Given a string s, cut s into some substrings such that every substring is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example
Given s = "aab",
Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.
Tags Dynamic Programming
*/
public class PalindromePartitioningIIPractice {
/**
* @param s a string
* @return an integer
*/
private boolean[][] getIsPalindrome(String s) {
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < s.length() - 1; i++) {
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int length = 2; length < s.length(); length++ ) {
for (int start = 0; start + length < s.length(); start++) {
isPalindrome[start][start + length] = (s.charAt(start) == s.charAt(start + length) && isPalindrome[start + 1][start + length - 1]);
}
}
return isPalindrome;
}
private int minCut(String s) {
//initialize
boolean[][] isPalindrome = getIsPalindrome(s);
int[] f = new int[s.length() + 1];
for (int i = 0; i <= s.length(); i++) {
f[i] = i - 1;
}
//main
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (isPalindrome[j][i - 1]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
return f[s.length()];
}
public static void main(String[] args) {
PalindromePartitioningIIPractice test = new PalindromePartitioningIIPractice();
int result = test.minCut("abba");
System.out.println("Expected: 0");
System.out.println(result);
}
}