# Java O(n^2) solution, I want to know if it's possible to use just one double loop.

• ``````public int minCut(String s) {
int len = s.length();
if(len == 1) return 0;
char[] array = s.toCharArray();
boolean[][] cuts = new boolean[len][len];
int[] res = new int[len];
cuts[0][0] = true;
for(int i=1; i<len; i++){
cuts[i][i] = true;
cuts[i][i-1] = true;
}
for(int i=1; i<len; i++){
for(int j=0; j<len-i;j++) {
if(array[j] == array[j+i] && cuts[j+1][j+i-1]) {
cuts[j][j+i] = true;
} else {
cuts[j][j+i] = false;
}
}
}
for(int i=0; i<len; i++) {
int min = i;
for(int j=0; j<=i; j++) {
if(cuts[j][i]) {
min = Math.min(min, j == 0 ? 0 : res[j-1] + 1);
}
}
res[i] = min;
}
return res[len-1];
}
``````

First create a two dimensional array that cuts[i][j] means whether string from i to j can form a Palindrome. Then use this cuts array to determine result. The logic is: if string from j to i can form a Palindrome, then we can use (the smallest) res[j-1]+1 to represent res[i].

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