有效的括号

题目信息

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()[]{}"
输出：true

示例 2：

输入：s = "{[]}"
输出：true

示例 3：

输入：s = "([)]"
输出：false

解题思路

1. 暴力破解
2. 无效操作分析
3. 优化方法：
   1. 对应消除与先进后出的问题优先考虑栈的使用
   2. 奇数长度的字符串不用判断，一定不会完全匹配
4. 考虑边界
5. 编码实现：遍历所有字符
   1. 如果遇到了左括号，就把对应的右括号压栈
   2. 如果遇到了右括号
      2.1 如果栈为空，该右括号无法形成闭合有效
      2.2 栈不为空，弹出栈顶元素判断是否能够成闭合
   3. 遍历完毕，栈为空则全部括号都完成闭合匹配，不为空则还有未闭合的括号存在

代码

class Solution {
    public boolean isValid(String s) {
        // 奇数个绝对不可能对应匹配
        if (s == null || s.trim().length() % 2 != 0) {
            return false;
        }
        // 对应消除，首选栈
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        // 遇到左括号便将对应右括号入栈
        for (char c: chars) {
            if(c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != c) {
                // 1. 栈为空，该右括号无法构成闭合
                // 2. 弹栈并判断是否是预期的右括号
                return false;
            }
        }
        // 循环完毕，检查是否还有没有匹配到的，即栈是否为空
        return stack.isEmpty();
    }
}

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/valid-parentheses

商业转载请联系官方授权，非商业转载请注明出处。