LeetCode. 20. Valid Parentheses

[Link] https://leetcode.com/problems/valid-parentheses/

Approach

Scan the string from left to right while keeping unmatched opening brackets in a stack. Before processing each character, the stack contains exactly the opening brackets that have been seen but not yet matched, in their original order. Therefore, when a closing bracket appears, it must match the most recently seen opening bracket. If the stack is empty or the types do not match, the string is invalid. After the scan, the string is valid only if the stack is empty; otherwise, an opening bracket was left unmatched.

The problem constraints guarantee that the string contains only ()[]{}. Each character is processed once, so the time complexity is O(N). In the worst case, all characters are opening brackets, so the auxiliary space complexity is O(N).

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
                continue;
            }

            if (stack.isEmpty()) {
                return false;
            }

            char opener = stack.pop();
            if ((c == ')' && opener != '(')
                    || (c == '}' && opener != '{')
                    || (c == ']' && opener != '[')) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}