Why timeExceed?


  • 0
    X
    private static HashMap<String, Integer> minCutMap = new HashMap<String, Integer>();//memorize the minCutMap
    private static HashMap<String, Boolean> palindromeMap = new HashMap<String, Boolean>();//memorize the palindrome
    
    public static int minCut(String s) {
        if (s==null||s.length()==0||s.length() == 1||isPalindrome(s)) {//if is Palindrome return true directly
            return 0;
        } else {
            if (minCutMap.get(s) != null) {
                return minCutMap.get(s);
            }
            Integer min = null;
            for (int start = 0; start < s.length(); start++) {
                if (isPalindrome(s.substring(0, start + 1))) {
                    int cut = 1 + minCut(s.substring(start + 1, s.length()));
                    if (min == null || cut < min) {
                        min = cut;
                    }
                }
            }
            minCutMap.put(s, min);
            return min;
        }
    }
    
    private static boolean isPalindrome(String substring) {//check if is Palindrome
        if (substring.length() == 1) {
            return true;
        } else {
            if (palindromeMap.get(substring) != null) { //check it
                return palindromeMap.get(substring);
            }
            boolean isPalindrome = false;
            if (substring.length() == 2) {
                isPalindrome = substring.charAt(0) == substring.charAt(1);
            } else {
                isPalindrome = substring.charAt(0) == substring.charAt(substring.length()-1) && isPalindrome(substring.substring(1, substring.length() - 1));
            }
            palindromeMap.put(substring, isPalindrome);//memorize it
            return isPalindrome;
        }
    }
    

    This is my code, and it always got time Exceed error, can anyone help me ?


  • 0
    F

    Hi, Xiaojie.

    I found three parts in your code where improvement can be made:

    1. The isPalindrome(String substring) method is not efficient enough. The following is a classic one:
    private boolean isPalindrome(String s) {
        int m = 0, n = s.length() - 1;
    
        while (m < n) {
    	  if (s.charAt(m++) != s.charAt(n--)) return false;
        }			
    
        return true;
    } 
    
    1. The starting point in the for loop is not necessary from 1, especially when you encounter the case where the string starts with pattern aaaaaaaaaaaaaaaaaa.... The idea is that no matter how many a are here, we can always treat them as one character. Therefore we only need to start from the index where the last a is.(provided there are more than one a here)
    1. The condition if (min == null || cut < min) in the for loop is not good. So we need to assign min an initial value. What would be a reasonable one? Just think about it, for every string that is not empty, you can at least find one way to cut the string such that all substrings are palindromes: all substrings contains only one letter. And this is the maximum value the minCut(String s) method should return. Therefore, it's reasonable to assign min this initial value and then compare min with the actual number of cuts you can get later and replace min with the new values if the new values are smaller.

    By the way, I modified you code and it got accepted. And nice thought for top-down DP there! Good luck!


  • 0
    F

    Sorry, I just found out that the second part in my comment is incorrect. And actually the OJ missed the special cases for testing this. That's why the modified code got accepted. Please discard part 2 in my comment and come up with a way to deal with strings starting with something like "aaaaaaaaaaaaaa...".


  • 0
    F

    My comment in part 2 stands under one condition: we should start from the index of 'a' where the rest of the string is a palindrome or from the index where the last 'a' character is, whichever index comes first.


Log in to reply
 

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