20. Valid Parentheses

Условие

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1: Input: s = "()" Output: true

Example 2: Input: s = "()[]{}" Output: true

Example 3: Input: s = "(]" Output: false

Code snippet: class Solution { public boolean isValid(String s) {

}

}

Ответ

Use a stack of opening brackets. Each closing bracket must match the most recent unmatched opening bracket; after scanning the string, the stack must be empty.

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

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ((c == ')' && open != '(')
                    || (c == ']' && open != '[')
                    || (c == '}' && open != '{')) return false;
            }
        }
        return stack.isEmpty();
    }
}

The input contract permits only bracket characters. A mismatched pair or an unmatched closing bracket fails immediately. Remaining opening brackets also invalidate the string. Time is O(n), and worst-case auxiliary space is O(n). The empty string is valid under the stated matching rules.