O(n^2) TLE Palindrome Partitioning II


  • 4
    E

    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;
    	
    	
    	
    	
    	
    }

  • 14
    L

    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.)


  • 1
    M

    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 ?

  • 0
    C

    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).


  • 0
    C

    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.


  • 0
    D

    very smart observation! thank you


Log in to reply
 

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