The link to the problem: https://leetcode.com/problems/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, when input s = "aab"
the output is 1 since once we cut s into "aa" and "b", we can get 2 palindrome strings.Thoughts:
This problem is the transformation of 131. Palindrome Partitioning. In problem 131, we are asked to find all the possible palindrome partitions. We can use backtracking to solve that problem.
In the helper method, we will see if we can divide the string that starts with a certain position i into all valid palindrome strings (can be the string itself, or smaller strings). We will choose a certain position k to cut once we found the part from the starting point i to k of the string is a palindrome. Then, we will again choose what’s the next cut for the string that starts with k+1.
….
Until we cannot choose our next cut, we keep redoing our cut and back to our previous cut and choose to find our “next cut” again.
Hence we can solve problem 131 like the below 8 ms code that beats 67% -
public List<List<String>> partition(String s) {
List<List<String>> rst = new ArrayList<>();
helper(rst,new ArrayList<>(), s, 0, s.length()-1);
return rst;
}
public void helper(List<List<String>> rst, List<String> inner,String s, int i,int j){
if(i>j)
{
rst.add(new ArrayList<>(inner));
return;
}
for(int k=i;k<=j;k++)//cut on k
{
if(!isPalindrome(s,i,k)) //skip
continue;
inner.add(s.substring(i,k+1)); //decide to cut
helper(rst,inner,s, k+1,j);
inner.remove(inner.size()-1); //redo the previous cut
}
}
public boolean isPalindrome(String s,int i,int j){
if(i==j)
return true;
while(i<j)
{
if(s.charAt(i++)!=s.charAt(j--))
return false;
}
return true;
}However, this problem doesn’t require us to return all the possible answers. We just want to know the minimum cuts we needed to make all the partitions as a valid palindrome.
Hence, if we do some modification to the above code, it will be like —
public int minCut(String s) {
return helper(s,0,s.length()-1,0);
}
public int helper(String s,int i,int j,int cuts){
if(isPalindrome(s,i,j))
return cuts;
int min = s.length();
for(int k=i;k<=j;k++) //cut on k
{
if(isPalindrome(s,i,k))
min = Math.min(min, helper(s,k+1,j,cuts+1));
}
return min;
}
public boolean isPalindrome(String s,int i,int j){
if(i==j)
return true;
while(i<j)
{
if(s.charAt(i++)!=s.charAt(j--))
return false;
}
return true;
}The above code will pass most of the test cases on Leetcode and failed in the last three cases due to Time Limit Exceeded. It failed on this but not problem 131 is because the possible input length of the string in this problem is much longer than the previous one. And Since we are using backtracking and find all the possible combinations of all the palindrome combinations in the string, the time complexity is exponential.
Hence, let’s see what can we do to improve the time complexity.
Code Logic:
Maybe we can solve the problem using dynamic programming for helping us speed up a little bit. We use dynamic programming to help us memorize the result of substrings, so later we can use the information instead of calling the method recursively.
We create a dp array to store the minimum cuts needed from index 0 to a certain position of the string. For example, dp[2] represents the minimum cut needed for the first three letters to be all palindrome strings.
⚠️In the below paragraph, I will use s[x,y] represents the part of the string s between position x and y. For example, for a string s like “abcde”, s[0,2] means “abc”.
In each iteration when we are trying to find the minimum value for dp[i], we will traverse every position before i and see if we can cut right there. When we found that s[k, i] is a palindrome, we decide to cut at the position k. Hence, we will cut the string s into s[0, k-1] and s[k, i]. We know that s[k, i] is a valid palindrome, and we also know that we can make dp[k-1] cut for s[0, k-1] to make s[0, k-1] all valid palindromes. Hence, we will need at least dp[k-1]+1 (plus one for cutting at position k) if we want to make a cut at k! 🔪 We will keep finding k from 0 to i, and find our minimum cut for s[0,i].
Below is the 968ms code that beats 17% —
public int minCut(String s) {
int n = s.length();
//dp[i] stores the minimum cut needed for s [0,i]
int[] dp = new int[n];
Arrays.fill(dp,n);
for(int i=0;i<n;i++)//ending point
{
for(int k=0;k<=i;k++) //make a cut
{
if(isPalindrome(s,k,i))
{
if(k==0)
{
dp[i] = 0; //best case
break;
}
dp[i] = Math.min(dp[i],dp[k-1]+1);
}
}
}
return dp[n-1];
}
public boolean isPalindrome(String s,int left,int right){
while(left<right)
{
if(s.charAt(left++)!=s.charAt(right--))
return false;
}
return true;
}It is also wasting time calling the isPalindrome(s, left, right) method if we already know the “smaller string is not palindrome at all”. For example, if we know “abcda” is not a palindrome, it is wasting time for us to check whether “xabcdax” is a palindrome.
We can also use a 2D array to help us record all the palindrome substrings. isValid[i][j] represents if s[i,j] is a palindrome; we can use s[i+1,j-1] to help us check if s[i,j] is valid.
✏️If the gap between the two positions i and j is too close, we don’t need to check if s[i+1,j-1] is valid or not. If they have the same letter, we will just consider the string as a palindrome. For example, we know “aa” and “aba” are palindromes without checking “whether its inner string is a palindrome”.
Since we need to depend on a smaller string to see if a longer string is a palindrome or not, we need to first assign the value from a smaller length to make the 2D array works as we wish.
In each different length from 1 to length n, we will assign a value to isValid[i][j] represents whether the string with starting point i and ending point j is a palindrome or not.
Below is the 13ms code that beats 57% —
public int minCut(String s) {
int n = s.length();
boolean[][] isValid = new boolean[n][n];
for(int len=1;len<=n;len++) //length of string
{
for(int i=0;i<=n-len;i++) // left
{
int j=i+len-1; //right
if(s.charAt(i)!=s.charAt(j))
continue;
if(j-i<=2)
isValid[i][j] = true;
else
isValid[i][j] = isValid[i+1][j-1];
}
}
int[] dp = new int[n];
Arrays.fill(dp,n);
for(int i=0;i<n;i++)
{
for(int k=0;k<=i;k++)
{
if(isValid[k][i])
{
if(k==0)
{
dp[i] = 0; //best case
break;
}
dp[i] = Math.min(dp[i],dp[k-1]+1);
}
}
}
return dp[n-1];
}👷Since it is not that straightforward to see how we can store whether if s[i,j] is a palindrome in a 2D array at first, I also draw some steps of how the 2D array varies using an example s = “aabbac”.
⚠️We only care about the cells that i is less than equal to j. Since it is impossible to have a substring that the starting point is greater than its ending point.
🔧Step 0. Initial State of the 2D array. We use isValid[i][j] to represent whether s[i,j] is a valid palindrome. Hence, if you want to see whether “bbac” is a palindrome, you will need to check the cell at (2,5).
🔧Step 1. We will start to assign values when the gap between starting position i and ending position j is 0. (i.e., the one-length string)
Since one letter is a palindrome, all the isValid[i][i] is True.
🔧Step 2. Find all the two-length strings and see if they are palindromes.
We only found that “aa” and “bb” are palindromes.
🔧Step 3. Find all the three-length strings and see if they are palindromes.
⚠️In step 1 to 3, we only need to check if the letter at i and letter at j is the same or not.
🔧Step 4. Find all the four-length strings and see if they are palindromes.
⚠️Start from this step, we not only check if the letter at i and j are the same but also if the “inner string” is a palindrome. (check its down left cell)
e.g., we found that s[1,4] is a palindrome since [2,3] is a palindrome.
🔧Step 5. Find all the five-length strings and see if they are palindromes.
(Although letter at 0 and letter at 4 are the same, we consider s[0,4] not a palindrome because s[1,3] is not a palindrome.)
🔧Step 6. We check if our one and only string that has a length of six is a palindrome or not.
