[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
921. Minimum Add to Make Parentheses Valid
1111. Maximum Nesting Depth of Two Valid Parentheses Strings
1003. Check If Word Is Valid After Substitutions
1249. Minimum Remove to Make Valid Parentheses
1541. Minimum Insertions to Balance a Parentheses String
1963. Minimum Number of Swaps to Make the String Balanced
2116. Check if a Parentheses String Can Be Valid