Got TLE when using dp memorization


  • 0
    S

    I am using an array to cache the overlap subproblems but still got TLE,
    Please help me to find the bottleneck

     public int minCut(String s) {
    		int []dp = new int [s.length() + 1 ];
    		for (int i = 0 ; i <= s.length() ; ++i) {
    			dp[i] = -1;
    		}		
    	    return doGet (s, 0, dp) - 1;    
    	 }
    	 
    	 
    	 public int doGet (String s , int start,int []dp){
    		 if (start >= s.length()) return 0 ;
    		 int min = Integer.MAX_VALUE ;
    		 for (int i = start ; i < s.length() ; ++i) {
    			  String curr = s.substring(start, i + 1) ;			  
    			  if (isPalindrome (curr) ) {			
    				  if (dp[i + 1] == -1) {
    					  dp [i + 1] = doGet (s ,  i + 1, dp) ;
    				  }
    				  int c = 1 + dp [i + 1] ;				  
    				  min = Math.min(c, min) ;
    			  }
    		 }
    		 return min;
    	 }
    	 
    	 public boolean isPalindrome(String s){
    		 for (int i = 0 , j = s.length() - 1 ; i < j ; ++i , --j) {
    			 if (s.charAt(i) != s.charAt(j)) return false ;
    		 }
    		 return true ;
    	 }

Log in to reply
 

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