132. Palindrome Partitioning II

  • 23.7%

https://leetcode.com/problems/palindrome-partitioning-ii/#/description

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.

1
2
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

13ms, September 22, 2016

https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space

My solution does not need a table for palindrome, is it right ? It uses only O(n) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<int> cut(n+1, 0); // number of cuts for the first k characters
for (int i = 0; i <= n; i++) cut[i] = i-1;
for (int i = 0; i < n; i++) {
for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
}
return cut[n];
}
};

https://discuss.leetcode.com/topic/2048/my-dp-solution-explanation-and-code

My DP Solution ( explanation and code)

Calculate and maintain 2 DP states:

  1. pal[i][j] , which is whether s[i..j] forms a pal
  2. d[i], which is the minCut for s[i..n-1]

Once we comes to a pal[i][j]==true:

  • if j==n-1, the string s[i..n-1] is a Pal, minCut is 0, d[i]=0;
  • else: the current cut num (first cut s[i..j] and then cut the rest s[j+1…n-1]) is 1+d[j+1], compare it to the exisiting minCut num d[i], repalce if smaller.

d[0] is the answer.

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) {
if(s.empty()) return 0;
int n = s.size();
vector<vector<bool>> pal(n,vector<bool>(n,false));
vector<int> d(n);
for(int i=n-1;i>=0;i--)
{
d[i]=n-i-1;
for(int j=i;j<n;j++)
{
if(s[i]==s[j] && (j-i<2 || pal[i+1][j-1]))
{
pal[i][j]=true;
if(j==n-1)
d[i]=0;
else if(d[j+1]+1<d[i])
d[i]=d[j+1]+1;
}
}
}
return d[0];
}
};

https://discuss.leetcode.com/topic/19298/two-c-versions-given-one-dp-28ms-one-manancher-like-algorithm-10-ms

Two C++ versions given (one DP 28ms, one Manancher-like algorithm 10 ms)

One typical solution is DP based. Such solution first constructs a two-dimensional bool array isPalin to indicate whether the sub-string s[i..j] is palindrome. To get such array, we need O(N^2) time complexity. Moreover, to get the minimum cuts, we need another array minCuts to do DP and minCuts[i] saves the minimum cuts found for the sub-string s[0..i-1]. minCuts[i] is initialized to i-1, which is the maximum cuts needed (cuts the string into one-letter characters) and minCuts[0] initially sets to -1, which is needed in the case that s[0..i-1] is a palindrome. When we construct isPalin array, we update minCuts everytime we found a palindrome sub-string, i.e. if s[i..j] is a palindrome, then minCuts[j+1] will be updated to the minimum of the current minCuts[j+1] and minCut[i]+1(i.e. cut s[0..j] into s[0,i-1] and s[i,j]). At last, we return minCuts[N].
So the complexity is O(N^2). However, it can be further improved since as described above, we only update minCuts when we find a palindrome substring, while the DP algorithm spends lots of time to calculate isPalin, most of which is false (i.e. not a palindrome substring). If we can reduce such unnecessary calculation, then we can speed up the algorithm. This can be achieved with a Manancher-like solution, which is also given as following.

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
// DP solution
class Solution {
public:
int minCut(string s) {
const int N = s.size();
if(N<=1) return 0;
int i,j;
bool isPalin[N][N];
fill_n(&isPalin[0][0], N*N, false);
int minCuts[N+1];
for(i=0; i<=N; ++i) minCuts[i] = i-1;

for(j=1; j<N; ++j)
{
for(i=j; i>=0; --i)
{
if( (s[i] == s[j]) && ( ( j-i < 2 ) || isPalin[i+1][j-1] ) )
{
isPalin[i][j] = true;
minCuts[j+1] = min(minCuts[j+1], 1 + minCuts[i]);
}
}
}
return minCuts[N];

}
};

The Manancher-like solution scan the array from left to right (for i loop) and only check those sub-strings centered at s[i]; once a non-palindrome string is found, it will stop and move to i+1. Same as the DP solution, minCUTS[i] is used to save the minimum cuts for s[0:i-1]. For each i, we do two for loops (for j loop) to check if the substrings s[i-j .. i+j] (odd-length substring) and s[i-j-1.. i+j] (even-length substring) are palindrome. By increasing j from 0, we can find all the palindrome sub-strings centered at i and update minCUTS accordingly. Once we meet one non-palindrome sub-string, we stop for-j loop since we know there no further palindrome substring centered at i. This helps us avoid unnecessary palindrome substring checks, as we did in the DP algorithm. Therefore, this version is faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Manancher-like solution
class Solution {
public:
int minCut(string s) {
const int N = s.size();
if(N<=1) return 0;

int i, j, minCUTS[N+1];
for(i=0; i<=N; ++i) minCUTS[i] = i-1;

for(i=1;i<N;i++)
{
for(j=0;(i-j)>=0 && (i+j)<N && s[i-j]== s[i+j]; ++j) // odd-length substrings
minCUTS[i+j+1] = min(minCUTS[i+j+1], 1 + minCUTS[i-j]);

for(j=0;(i-j-1)>=0 && (i+j)<N && s[i-j-1]== s[i+j]; ++j) // even-length substrings
minCUTS[i+j+1] = min(minCUTS[i+j+1], 1 + minCUTS[i-j-1]);
}
return minCUTS[N];
}
};

https://discuss.leetcode.com/topic/22388/56-ms-python-with-explanation

56 ms python with explanation

Algorithm (460 ms) credits go to:

https://leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

The main algorithm idea is if s[i,j] is a palindrome, then the minCut(s[:j]) is at most minCut(s[:i-1])+1. This literally needs to find out all possible palindromes in the list. The above post provides an efficient search algorithm. O(n) space and O(n^2) time complexity.

Further acceleration (460 ms -> 56 ms) credits go to:

https://leetcode.com/discuss/43950/python-100ms-extra-dealing-super-cases-reduces-576ms-100ms

The main idea for acceleration is to quickly check and exclude a few long palindrome tests..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minCut(self, s):
# acceleration
if s == s[::-1]: return 0
for i in range(1, len(s)):
if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
return 1
# algorithm
cut = [x for x in range(-1,len(s))] # cut numbers in worst case (no palindrome)
for i in range(len(s)):
r1, r2 = 0, 0
# use i as origin, and gradually enlarge radius if a palindrome exists
# odd palindrome
while i-r1 >= 0 and i+r1 < len(s) and s[i-r1] == s[i+r1]:
cut[i+r1+1] = min(cut[i+r1+1], cut[i-r1]+1)
r1 += 1
# even palindrome
while i-r2 >= 0 and i+r2+1 < len(s) and s[i-r2] == s[i+r2+1]:
cut[i+r2+2] = min(cut[i+r2+2], cut[i-r2]+1)
r2 += 1
return cut[-1]

The following code simply implements the algorithm without any optimization (1800 ms), and should be easier to understand. O(n) space and O(n^3) time complexity.

1
2
3
4
5
6
7
def minCut(self, s):
cut = [x for x in range(-1,len(s))]
for i in range(0,len(s)):
for j in range(i,len(s)):
if s[i:j] == s[j:i:-1]:
cut[j+1] = min(cut[j+1],cut[i]+1)
return cut[-1]

https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36

Easiest Java DP Solution (97.36%)

This can be solved by two points:

  1. cut[i] is the minimum of cut[j - 1] + 1 (j <= i), if [j, i] is palindrome.
  2. If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i].

The 2nd point reminds us of using dp (caching).

1
2
3
4
a   b   a   |   c  c
j i
j-1 | [j, i] is palindrome
cut(j-1) + 1

Hope it helps!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];
boolean[][] pal = new boolean[n][n];

for(int i = 0; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true;
min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
}
}
cut[i] = min;
}
return cut[n - 1];
}
谢谢你,可爱的朋友。