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


  • 2
    T

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

    }


Log in to reply
 

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