README_EN.md

20. Valid Parentheses

中文文档

Description

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"

Output: true

Example 2:

Input: "()[]{}"

Output: true

Example 3:

Input: "(]"

Output: false

Example 4:

Input: "([)]"

Output: false

Example 5:

Input: "{[]}"

Output: true

Solutions

Python3

class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return True
        helper = []
        for c in s:
            if c in '([{':
                helper.append(c)
            else:
                if len(helper) == 0 or (helper.pop() + c) not in ["()", "[]", "{}"]:
                    return False
        return len(helper) == 0

Java

class Solution {
    public boolean isValid(String s) {
        if (s == null || s == "") {
            return true;
        }
        char[] chars = s.toCharArray();
        Stack<Character> helper = new Stack<>();
        for (char c : chars) {
            boolean isLeft = c == '(' || c == '[' || c == '{';
            if (isLeft) {
                helper.push(c);
            } else {
                if (helper.isEmpty() || !match(helper.pop(), c)) {
                    return false;
                }
            }
        }
        return helper.isEmpty();
    }

    private boolean match(char left, char right) {
        return (left == '(' && right == ')')
            || (left == '[' && right == ']')
            || (left == '{' && right == '}');
    }
}

...