# It's easy to go from the O(n^3) solution to O(n^2)

• most people (including me) came up with the DP solution that uses 2 levels of loops, in the inner loop, isPalindrome() is called, which makes the total time to O(n^3). but this solution https://leetcode.com/discuss/10174/my-accepted-o-n-2-dp-solution-in-java uses a smart technique to store the isPalindrome() results in a table , so the call essentially takes O(1) time, and the table construction takes O^(N^2) time, by using DP again.

I modified his code a little bit so the overall structure and flow is still same as the n^3 algorithm, just changed the internals of isPalindrome() . hope this is easier to illustrate the idea

``````public class Solution {
public int minCut(String s) {

return partition(s);
}

boolean isPal[][];

public int partition(String s) {
int m = s.length();
isPal = new boolean[m][m];
final char []ss = s.toCharArray();
buildIsPal(ss);

int [] solutionsEnding = new int[m];

for(int i=0;i<m;i++) {
solutionsEnding[i] = Integer.MAX_VALUE;
for(int j=i-1;j>=-1;j--) {
if (isPalindrome(ss, j+1, i)) {
int prefix;
if (j>=0)

prefix = solutionsEnding[j];
else
prefix = 0;

solutionsEnding[i] = Math.min(solutionsEnding[i], prefix+1);
}
}
}

return solutionsEnding[m-1]-1;
}

void buildIsPal(char[]ss) {
for(int i=0;i<ss.length;i++)
isPal[i][i] = true;
for(int i=0;i<ss.length-1;i++)
isPal[i][i+1] = ss[i] == ss[i+1];

for(int i=2;i<ss.length;i++)
for(int j=0;j+i<ss.length;j++)
isPal[j][j+i] = isPal[j+1][j+i-1] && (ss[j] == ss[j+i]);
}

boolean isPalindrome(char ss[] , int start, int end) {
return isPal[start][end];
}
``````

}

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