Question
Formatted question description: https://leetcode.ca/all/132.html
132 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.
@tag-dp
Algorithm
One-dimensional dp array, where dp[i]
represents the minimum number of divisions in the range of substring [0, i].
Use a two-dimensional dp array p, where p[i][j]
indicates whether the substring in the interval [i, j]
is a palindrome, and the state transition equation is p[i][j] = (s[i] == s[j]) && p[i+1][j-1]
, where p[i][j] = true
if [i, j]
is a palindrome.
Code
Java
public class Palindrome_Partitioning_II {
/*
* @note: 这题,我自己的思路有了点问题。如果i-j是pal,那么i的cut数应该是j+1的cut数加1。
* 我想成了i的cut数等于j的cut数,逻辑错误
*
* 这题最好的地方,是用了两个dp的数组,一个标记是不是pal,一个数cut的数目 而不是单纯的一个dp数组
*/
public class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return -1;
}
// 'abcba', when reaching 'c', minCut=2
// when reaching 2nd 'b', minCut=1
// when reaching 2nd 'a', minCut=0
// so, if a substring is palindrome, cut is prev_segment+1
// set up a fast lookup for if palindrome from i to j
boolean[][] isPal = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
for (int j = i; j >= 0; j--) {
if (i == j || (s.charAt(i) == s.charAt(j) && (i - j == 1 || isPal[j + 1][i - 1]))) {
isPal[j][i] = true; // j is first, then i
}
}
}
// set up min count array, worst case, each char is a palindrome
int[] minCut = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
minCut[i] = i;
}
// how to cound, eg: 'aabcba', 'aabcbaz'
// @note: if a substring is palindrome, cut is prev_segment+1
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < s.length(); j++) {
if (isPal[i][j]) {
if (i - 1 >= 0) { // @note: eg, 'aabcba'
minCut[j] = Math.min(minCut[j], 1 + minCut[i - 1]);
} else { // i.e., i==0. eg, 'abcba'
minCut[j] = 0;
}
}
}
}
int min = minCut[s.length() - 1];
return min;
}
}
public class Solution_slow {
List<List<String>> list = new ArrayList<>();
public int minCut(String s) {
if (s == null || s.length() == 0) {
return -1;
}
find(s, new ArrayList<String>());
int min = Integer.MAX_VALUE;
for (List<String> each : list) {
min = Math.min(min, each.size() - 1);
}
return min;
}
private void find(String s, ArrayList<String> currentList) {
if (s.length() == 0) {
list.add(currentList);
return;
}
// idea is, scan from index=0, to find each palindrome, then rest substring to next recursion
for (int i = 0; i < s.length(); i++) {
String sub = s.substring(0, i + 1); // @note: substring 0-s[i]
System.out.println("substring is: " + sub);
if (isPal(sub)) {
ArrayList<String> nextList = new ArrayList<>(currentList); // deep copy
nextList.add(sub);
find(s.substring(i + 1), nextList);
}
}
}
private boolean isPal(String s) {
int i = 0;
int j = s.length() - 1;
while (i <= j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
}