Java weird behavior of OJ, one AC other TLE same O(n) algorithm


  • 0

    This is my implementation which TLE

    public class Solution {
        public int longestValidParentheses(String s) {
            if (s == null || s.length() < 2)
                return 0;
            int n = s.length();
            Stack<Integer> stack = new Stack<>();
            int left = -1;
            char c;
            int max = 0;
            for (int i = 0; i < n; i++) {
                c = s.charAt(i);
                if (c == '(')
                    stack.push(i);
                else {
                    if (!stack.isEmpty()) {
                        stack.pop();
                        max = Math.max(max, i - (stack.isEmpty() ? left : stack.peek()));
                    } else {
                        left = i;
                    }
                }
            }
            return max;
        }
    }
    

    But it actually follows another good one in the forum which is accepted! The logic is the same. How come?

    public class Solution {
        public int longestValidParentheses(String s) {
            if (s == null || s.length() < 2)
                return 0;
            Stack<Integer> stack = new Stack<>();
            int n = s.length();
            char c;
            int max = 0;
            int left = -1; // left bound, 1 to the left of new starting (
            for (int i = 0; i < n; i++) {
                c = s.charAt(i);
                if (c == '(') {
                    stack.push(i);
                } else if (stack.isEmpty()) { 
                    left = i; 
                } else { 
                    stack.pop();
                    if (!stack.isEmpty())
                        max = Math.max(max, i - stack.peek()); 
                    else 
                        max = Math.max(max, i - left);
                }
            }
            return max;
        }
    }

Log in to reply
 

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