Time limits (TLE) against Python in the second contest in a row. Compared with Go (AC)


  • 0
    L

    There is a trivial recursive solution (with only one counter):

    def checkValidString(self, s):
        def doit(s, cnt):
            if cnt < 0:
                return False
            if s == "":
                if cnt == 0:
                    return True
                else:
                    return False
            if s[0] == '(':
                return doit(s[1:], cnt + 1)
            if s[0] == ')':
                return doit(s[1:], cnt - 1)
            return doit(s[1:], cnt + 1) or doit(s[1:], cnt) or doit(s[1:], cnt - 1)
        return doit(s, 0)
    

    This solution is not accepted because of TLE. But the same solution in Go is accepted (~650 ms).

    func doit(s string, cnt int) bool {
    	if cnt < 0 { return false }
    	if s == "" { return cnt == 0 }
    	if s[0] == '(' { return doit(s[1:], cnt + 1) }
    	if s[0] == ')' { return doit(s[1:], cnt - 1) }
    	if s[0] == '*' {
    		return doit(s[1:], cnt + 1) || doit(s[1:], cnt - 1) || doit(s[1:], cnt)
    	}
    	return false
    }
    
    func checkValidString(s string) bool {
    	return doit(s, 0)    
    }
    

    Of course this is not an optimal solution but time limits for different languages are not fair enough. Remember Problem "675. Cut Off Trees for Golf Event".

    P.S. Another example is with MLE error for Python in the problem "479. Largest Palindrome Product", where Java solution works well. For Javascript situation is even worse.


Log in to reply
 

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