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.
For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.
Analysis
The first solution is a one which is almost the same with the standard solution to Matrix Multiplication. We use to record the minimum number of cuts between and , which can be calculated by
.
However, there are some redundant and unnecessary operations involved. Instead of computing for all possible pairs , can we find a solution that reduces the amount of computation? The answer is yes.
Let us define a new variable . In Solution 2, we only compute , i.e. .
For the substring , we define to be the set of indices less than
then
- , if is NOT a palindrome
- , if is a palindrome
Below is the pseudo code of the algorithm. In this algorithm, can be precomputed in time. Therefore, the total time complexity is .
1 //pseudo code in mixed C++-Python style
2 for (int i = 0; i < n; ++ i)
3 if (is_palindrome[0][i])
4 minCut[i] = 0
5 else
6 minCut[i] = MAX_INT
7 for (int j = 0; j < i; ++ j)
8 if (is_palindrome[j+1][i])
9 minCut[i] = min(minCut[i], minCut[j] + 1);
10 return minCut[n-1]Solution
solution
If you run this code in leetcode OJ, you will get runtime error, as there is a test case where the length of the string is more than 1400. Allocating a 2-D int array with elements leads to runtime error.
You can replace int num[n][n] with unsigned char num[n][n], but it is still a nasty solution and will get you a TLE.
1 class Solution {
2 public:
3 int minCut(string s) {
4 int n = s.size();
5 if (!n) return 0;
6 int num[n][n];
7 for (int i = 0; i < n; ++ i)
8 memset(num[i], 0, sizeof(int) * n);
9
10 for (int i = 0; i < n - 1; ++ i)
11 num[i][i+1] = (s[i] != s[i+1]);
12
13 for (int len = 3; len <= n; ++ len){
14 for (int start = 0; start < n - len + 1; ++ start){
15 int end = start + len - 1;
16 if (num[start+1][end-1] == 0 && s[start] == s[end])
17 num[start][end] = 0;
18 else{
19 num[start][end] = 2100000000;
20 for (int k = start; k < end; ++ k)
21 num[start][end] = min(num[start][k]+num[k+1][end]+1, num[start][end]);
22 }
23 }
24 }
25 return num[0][n-1];
26 }
27 };solution
1 class Solution{
2 public:
3 int minCut(string s) {
4 int n = s.size();
5 if (!n) return 0;
6
7 // palindrome judgement
8 bool isPal[n][n];
9 for (int i = 0; i < n - 1; ++ i)
10 isPal[i][i] = true, isPal[i][i+1] = (s[i] == s[i+1]);
11 isPal[n-1][n-1] = true;
12
13 for (int len = 3; len <= n; ++ len)
14 for (int start = 0; start < n - len + 1; ++ start){
15 int end = start + len - 1;
16 isPal[start][end] = (s[start] == s[end]) && isPal[start+1][end-1];
17 }
18
19 //calculate minimum number of cut
20 int minCutArray[n];
21 minCutArray[0] = 0;
22 for (int i = 1; i < n; ++ i){
23 if (isPal[0][i]){
24 minCutArray[i] = 0;
25 continue;
26 }
27 minCutArray[i] = 2100000000;
28 for (int j = 0; j < i; ++ j ){
29 if (isPal[j+1][i])
30 minCutArray[i] = min(minCutArray[i], minCutArray[j] + 1);
31 }
32 }
33 return minCutArray[n-1];
34 }
35 };