# O(n^2) TLE Palindrome Partitioning II

• I used DP in 2 dimensional array to solve the palindrome problem and this cut problem. To avoid Arrays.fill(), I let both the value of pal[][] and cut[][] be of the true value+1. But it goes TLE in the "apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp" case, I used System.currentTimeMillis() and got it's 175ms to 230ms. Are there some more space to make improvement? Thanks.

``````    public static int pal(int i,int j,String s,int[][] pal){
if(pal[i][j]!=0)
return pal[i][j];

if(j-i<=1){
pal[i][j]=2;
return 2;
}

if(s.charAt(i)==s.charAt(j-1)){
pal[i][j]=pal(i+1,j-1,s,pal);
return pal[i][j];
}
else{
pal[i][j]=1;
return 1;
}
}

public static int cut(int i,int j,String s,int[][] cut,int[][] pal){

if(cut[i][j]!=0){
return cut[i][j];
}
if(pal(i,j,s,pal)==2){
cut[i][j]=1;
return 1;
}

int min=j-i;
int tmp=min;
for(int mid=i+1;mid<j;mid++){
tmp=cut(i,mid,s,cut,pal)+cut(mid,j,s,cut,pal);
if(tmp<min)
min=tmp;
if(tmp==2)
break;
}
cut[i][j]=min;

return min;
}
public static int minCut(String s) {
int len=s.length();
if(len<=1)
return 0;
int pal[][]=new int[len+1][len+1];
int cut[][]=new int[len+1][len+1];

return cut(0,len,s,cut,pal)-1;

}``````

• Your algorithm is in O(n^3), that's why you get a TLE.

You are computing `pal[][]` in O(n^2) and `cut[][]` in O(n^3). Let us first see why.
You defined `cut` by this mathematical formula:

``````cut[i][j] = Minimum number of cuts for the word s[i]...s[j];
cut[i][i] = 0 for 0 ≤ i < len)
cut[i][j] = min_{i < mid < j} { cut[i][mid] + cut[mid+1][j] } for all 0 ≤ i < j < s.len
``````

That last line takes O(n) time to compute, and you do it for the n^2 indices (i,j). Total O(n^3).

The key to improve your algorithm is to realize that you are computing too many non necessary values in `cut[][]`. Imagine you have already computed `cut[i][j-1]` and you now want to compute `cut[i][j]`. What can happen? That new letter creates palindromes that ends at index `j`. There could be several of them, and you have to examine if this creates new possible cuts. The formula becomes:

``````cut[i][j] = Minimum number of cuts for the word s[i]...s[j];
cut[i][j] = 0 if pal[i][j]
cut[i][j] = min_{i < mid < j} { cut[i][mid] + 1 if pal[mid+1][j] } for all 0 ≤ i < j < len
``````

Hey, this is still O(n^3)! Yes, but we are almost there. Note how now we only use the left part `cut[i][mid]` and never the right part `cut[mid+1][j]`. Since what we want is `cut[0][len-1]`, we will never need to compute a value `cut[i][j]` for `i≠0`, what that means, is that we only need the first row of `cut`. This is how we get back to O(n^2).

The final formula:

``````minCut[i] = Minimum number of cuts for the word s[0]...s[i];
minCut[0] = 0
minCut[i] = { 1 if pal[0][i]
{ min_{ 1 ≤ j ≤ i} {minCut[j] + 1 if pal[j][i]}
``````

Note that the set `{minCut[j] + 1 if pal[j][i]}` is not empty since `pal[j][j] == true`;

(A last note, you are doing a top-down approach with memoization. Usually the term
dp is reserved for the bottom-up approach.)

• Even this is O(n^3) algo:

1. As there is a third inner loop to check whether string[ j....i ] is a palindrome or not ?

• Check if substring[j..i] is a palindrome can precomputed ahead of time and saved in a array, thus the algorithm is O(n^2).

• Also the reason you don't need to compute the right part cut[mid+1][j] is because
cut[i, j-1] + cut[j,j] + 1 is always smaller than cut[i,mid] + cut[mid + 1][j] + 1 if substring[mid+1..j] is not a palindrome.

• very smart observation! thank you

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