I'm sure my algo is O(N^2) here. but why i'm still getting TLE on "aaa....aaa" test case?


  • 1
    A

    HashMap<String, Integer> mapStringCost = new HashMap<String, Integer>();

    public int minCut(String s) {
    	int cuts = s.length() - 1;
    	String ls = "";
    	
    	if (isPalindrome(s))
    		return 0;
    	
    	for (int i = 0; i < s.length(); i++){
    		ls += s.charAt(i);
    		if (isPalindrome(ls))
    		{
    			String lsub = s.substring(i+1);
    			if (lsub.isEmpty())
    				continue;
    			
    			Integer subMinCut = mapStringCost.get(lsub);
    			
    			if (subMinCut == null)
    			{
    				subMinCut = minCut(lsub);
    				mapStringCost.put(lsub, subMinCut);
    			}
    			
    			if (cuts > subMinCut + 1)
    				cuts = subMinCut + 1; 
    			
    		}
    		if (cuts == 1)
    			return cuts; // s itself isn't palindrome when we are here, so if cuts is 1, we are already the best. return here.
    	}
    	return cuts;
    }
    
    private boolean isPalindrome(String s)
    {
    	if (s.isEmpty())
    		return true;
    	boolean isPalindrome2 = true;
    	for (int i = 0; i < s.length()/2; i++)
    	{
    		char sfront = s.charAt(i);
    		char sback = s.charAt(s.length() - i - 1);
    		if (sfront != sback)
    		{
    			// found bad sequence, bail
    			isPalindrome2 = false;
    			break;
    		}
    	}
    	return isPalindrome2;
    }
    
    1. i'm using the hashmap to record the calculated mincuts for specific substring. this saved big, and serves the memoization part of the DP.
    2. i only have 2 for loops in this code, the main loop each iteration, and the isPalindrome function has a lopp. worst case ( if it's is a palindrome) will loop through entire substring.

    any suggestion i can improve further?


  • 0
    K

    Your solution is not O(N^2), is O(N^3).

    public int count = 0;
    public int count_of_minCut = 0;
    public int minCut(String s) {	
    int cuts = s.length() - 1;
    String ls = "";
    count_of_minCut++;
    
    if (isPalindrome(s))
        return 0;
    
    for (int i = 0; i < s.length(); i++){
        ls += s.charAt(i);
        count++;
        if (isPalindrome(ls))
        {
    

    If you edit your code as I pasted above, you can see that the code calls minCut s.length() times.

    For each minCut called, it will iterate through each character in s and test if ls is palindrome, thus O(N^2) time complexity for each mincut call.

    Therefore your solution will is O(N^3) in time complexity.


Log in to reply
 

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