How can I boost my program to O^2?


  • 1
    J

    my following program is running in O(n^3), and always get TLE
    please help me to boost it up

    public int minPalPartition2(String s){
        if(s==null) return -1;
        char[] str = s.toCharArray();
        int length = str.length;
        int[][] minCut= new int[length][length];
        boolean[][] isPal = new boolean[length][length];
        for(int i=0;i<length;i++){
            isPal[i][i]=true;
            minCut[i][i]=0;
        }
        for(int i=0;i<length;i++){
            for(int j=i+1;j<length;j++){
                int subLength = j-i+1;
                if(subLength==2)
                    isPal[i][j] = str[i]==str[j];
                else
                    isPal[i][j] = (str[i]==str[j]&&isPal[i+1][j-1]);
                if(isPal[i][j]==true)
                    minCut[j][j]=0;
                else{
                    minCut[i][j]=Integer.MAX_VALUE;
                    for(int k=i;k<j;k++){
                        minCut[i][j]=Math.min(minCut[i][j],minCut[i][k]+1+minCut[k+1][j]);
                    }
                }
            }
        }
        return minCut[0][length-1];
    }

  • 4
    L

    If you want O(n^2). you could think this: dp(i) = min( dp(j) + 1 ) for all j < i that isPal(j + 1, i); And you could calculate isPal before DP by O(n^2) as your code did. As a result, you only need O(n^2) to do DP. And dp(s.length()) is the final answer.


  • -1
    L

    I think there is something wrong with your calculation of isPal[i][j]. You cannot make sure that isPal[i+1][j-1] is calculated before calculating isPal[i][j]. The loop condition needs change.


  • 6
    R

    Here is an elegant DP solution, where dp[i] means min cut(+1) for the prefix of s with length i. The transition is natural for the monotonic property of palindrome strings. The p controls even/odd palindromes.

    class Solution {
    public:
        int minCut(string s) {
            int N = s.size();
            vector<int> dp(N+1,numeric_limits<int>::max());
            dp[0] = 0;
            for(int i=0;i<N;i++)
            for(int p=0;p<=1;p++)
            for(int l=0;l<=N;l++) {
                int a=i-l, b = i+l+p;
                if( a < 0 || b >= N || s[a]!=s[b] )
                    break;
                dp[b+1] = min(dp[b+1],dp[a]+1);
            }
            return dp[N]-1;
        }
    };

  • 0
    S

    This code is a little difficult to understand, which is really elegant.
    Note that i is the centre of a PAL string.
    and the L loop uses the previous comparation which is very useful to avoid time consuming.


Log in to reply
 

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