What did I get TLE error??


  • 0
    Q

    Credit to @EdickCoding his code is

        public int longestValidParentheses(String s) {
            LinkedList<Integer> stack = new LinkedList<>();
            int result = 0;
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
                    stack.pop();
                    result = Math.max(result, i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
            return result;
        }
    

    And I tried avoiding adding -1 to the stack so I had code like this:

        public static int longestValidParentheses(String s) {
            Stack<Integer> stack = new Stack<>();
            int result = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ')' && stack.size() > 0 && s.charAt(stack.peek()) == '(') {
                    stack.pop();
                    result = Math.max(result, stack.size() == 0 ? i + 1 : i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
            return result;
        }
    
    

    But this failed with TLE error. The test case was the one full of '('. I actually think that my code should run the same as @EdickCoding because for this test case, in the first "if" statement: if (s.charAt(i) == ')' && stack.size() > 0 && s.charAt(stack.peek()) == '(') , it should fail at the very first comparison s.charAt(i) == ')' and stop.

    I change the code a little and it went through:

        public int longestValidParentheses(String s) {
            Stack<Integer> stack = new Stack<>();
            int result = 0;
            for (int i = 0; i < s.length(); i++) {
            	if (s.charAt(i) == '(') {
            		stack.push(i); 
            	} else {
            		if (stack.size() > 0 && s.charAt(stack.peek()) == '(') {
            			stack.pop();
            			result = Math.max(result, stack.isEmpty() ? i + 1 : i - stack.peek());
            		} else {
            			stack.push(i);
            		}
            	}
                
            }
            return result;
        }
    

    Any ideas what is wrong?


Log in to reply
 

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