# How to get from O(n^3) to O(n^2) ? Java Solution Sharing

• I have been trapped by O(n^3) run time all the way till I finally found the correlation between Palindrome Partitioning and Palindrome Partitioning II.

In Palindrome Partitioning, we are able to get every pair of (i,j), such that s.substring(i,j) is or is not a palindrome. And it's O(n^2) to get there.

But if we are to trace on that 2D array to determine min cut, we are going into an O(2^n) recursive algorithm.

Based on what we already know, the s.substring(i,j) is or is not a palindrome, which is a very useful information, can we in O(n^2) time get the min cut of s?

The answer is another DP, whether you use a 2D array or a 1D array, you'll find that since we know whether s.substring(i,j) is or is not a palindrome, we can make each iteration O(1).

Two separate DP with both running in O(n^2) time makes a O(n^2) algorithm.

``````public class Solution {
public int minCut(String s) {
// use DP to determine any palindrome substring
boolean opt[][] = new boolean[s.length()][s.length()+1];
// base case
for(int i = 0;i < s.length();i++){
opt[i][i+1] = true;
opt[i][i] = true;
}
// iteration
for(int i = 2;i <= s.length();i++)
for(int j = 0;j+i <= s.length();j++)
opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];

// use DP to determine min cut
int cut[] = new int[s.length()+1];
for(int i = 1;i <= s.length();i++){
if(opt[0][i])
cut[i] = 0;
else{
cut[i] = i-1;
for(int t = 1;t < i;t++){
cut[i] = Math.min(cut[i],cut[t] + (opt[t][i]?1:i-t));
}
}
}
return cut[s.length()];

}
}``````

• This post is deleted!

• Great solution! But I'm a little confuse about the transform function.

cut[i] = Math.min(cut[i], cut[t] + (opt[t][i] ? 1 : i - t));

When opt[t][i] is false, just think substr(t, i - t) as a string with no palindrome inside ? I think it can be lower. Why does this solution works ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.