题目描述

题目链接：20. 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例1：

1 2	输入：s = "()" 输出：true

示例2：

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

示例3：

1 2	输入：s = "(]" 输出：false

提示：

1 <= s.length <= 10(4)
s 仅由括号 '()[]{}' 组成

我的题解

方法一：栈

思路

非常经典的栈类型题目，当栈顶字符与当前字符匹配时，出栈即可；反之入栈，类似于消除游戏。最终如果栈为空则表示为有效的括号。

代码

class Solution {
    public boolean isValid(String s) {
        if ((s.length() & 1) == 1) {
            return false;
        }
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!stack.isEmpty() && isMatch(stack.peek(), ch)) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

    private boolean isMatch(char source, char target) {
        return (source == '(' && target == ')') || (source == '[' && target == ']') || (source == '{' && target == '}');
    }
}