Time Limit Exceeded. How to improve???


  • 0
    N
    public class Solution {
    public int minCut(String s)
    {
    	int len = s.length();
    	int[] dp = new int[len];
    	for (int i = 0; i < len; i++)
    		if (isPal(s.substring(0, i + 1)))
    			dp[i] = 0;
    		else
    			dp[i] = Integer.MAX_VALUE;
    	for (int i = 0; i < len; i++)
    	{
    		if (dp[i] == 0)
    			continue;
    			
    		for (int j = 0; j < i; j++)
    		{
    			if (isPal(s.substring(j + 1, i + 1)))
    				if (dp[i] > dp[j] + 1)
    					dp[i] = dp[j] + 1;
    		}
    	}
    	return dp[len - 1];
    }
    
    private boolean isPal(String s)
    {
    	int len = s.length();
    	for (int i = 0; i < len; i++) {
    		if (s.charAt(i) != s.charAt(len - 1 - i))
    			return false;
    	}
    	return true;
    }}
    

    This is my code. dp[i] = MIN(dp[j] + 1) where ( j < i && isPal(s[j+1, i+1]) ).
    In eclipse, it spend about 1-2 seconds, but in leetcode it says "Time Limit Exceeded".


  • 3
    R

    1-2 seconds must be a TLE. No solution was allowed to have 1000ms in leetcode. Your solution is O(n^3) time complexity. So it must have some trouble to pass.

    Take a look of my solution. It uses a matrix to store the information of whether or not a substring is a palindrome.

    public class Solution {
       
    public int minCut(String s) {
        
        if (s==null||s.length()==0) return 0;
        
        int length=s.length();
        
        boolean[][] palindrome= new boolean[length][length];
        
        for (int i=0;i<length;i++)
            Arrays.fill(palindrome[i],false);
            
        int[] results = new int[length];
        
        for (int start=length-1;start>=0;start--){
            results[start]=length-start-1;
            for (int end=start;end<length;end++){
                if (s.charAt(start)==s.charAt(end)){
                    if (end-start<2)
                        palindrome[start][end]=true;
                    else 
                        palindrome[start][end]=palindrome[start+1][end-1];
                }
                if (palindrome[start][end])
                    if (end==length-1)
                        results[start]=0;
                    else
                    results[start]=Math.min(results[start],results[end+1]+1);
            }
        }
        return results[0];
    

    }
    }


Log in to reply
 

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