How to get from O(n^3) to O(n^2) ? Java Solution Sharing


  • 1
    S

    I have been trapped by O(n^3) run time all the way till I finally found the correlation between Palindrome Partitioning and Palindrome Partitioning II.

    In Palindrome Partitioning, we are able to get every pair of (i,j), such that s.substring(i,j) is or is not a palindrome. And it's O(n^2) to get there.

    But if we are to trace on that 2D array to determine min cut, we are going into an O(2^n) recursive algorithm.

    Based on what we already know, the s.substring(i,j) is or is not a palindrome, which is a very useful information, can we in O(n^2) time get the min cut of s?

    The answer is another DP, whether you use a 2D array or a 1D array, you'll find that since we know whether s.substring(i,j) is or is not a palindrome, we can make each iteration O(1).

    Two separate DP with both running in O(n^2) time makes a O(n^2) algorithm.

    public class Solution {
        public int minCut(String s) {
            // use DP to determine any palindrome substring
            boolean opt[][] = new boolean[s.length()][s.length()+1];
            // base case
            for(int i = 0;i < s.length();i++){
                opt[i][i+1] = true;
                opt[i][i] = true;
            }
            // iteration
            for(int i = 2;i <= s.length();i++)
                for(int j = 0;j+i <= s.length();j++)
                    opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1]; 
            
            
            // use DP to determine min cut
            int cut[] = new int[s.length()+1];
            for(int i = 1;i <= s.length();i++){
                if(opt[0][i])
                    cut[i] = 0;
                else{
                    cut[i] = i-1;
                    for(int t = 1;t < i;t++){
                        cut[i] = Math.min(cut[i],cut[t] + (opt[t][i]?1:i-t));
                    }
                }
            }
            return cut[s.length()];
            
        }
    }

  • 0
    V
    This post is deleted!

  • 0
    V

    Great solution! But I'm a little confuse about the transform function.

    cut[i] = Math.min(cut[i], cut[t] + (opt[t][i] ? 1 : i - t));

    When opt[t][i] is false, just think substr(t, i - t) as a string with no palindrome inside ? I think it can be lower. Why does this solution works ?


Log in to reply
 

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