[LeetCode] 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:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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

Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.

有效的括号。

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是用 stack 做。如果看到左半边括号就无条件压入栈；如果看到右半边括号，判断栈是不是为空，为空就报错；栈不为空再判断目前栈顶元素是不是相对应的左半边，若不是也报错。

复杂度

时间O(n)
空间O(n)

代码

Java实现

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

JavaScript实现

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(' || s[i] === '[' || s[i] === '{') {
            stack.push(s[i]);
        }
        if (s[i] === ')') {
            if (stack.length === 0 || stack.pop() != '(') return false;
        }
        if (s[i] === ']') {
            if (stack.length === 0 || stack.pop() != '[') return false;
        }
        if (s[i] === '}') {
            if (stack.length === 0 || stack.pop() != '{') return false;
        }
    }
    return stack.length === 0 ? true : false;
};

相关题目

20. Valid Parentheses
678. Valid Parenthesis String
1111. Maximum Nesting Depth of Two Valid Parentheses Strings
921. Minimum Add to Make Parentheses Valid
1541. Minimum Insertions to Balance a Parentheses String
1003. Check If Word Is Valid After Substitutions